I used Norton for several years and bought every version. I just got 2004 a couple months ago, and had similiar problems.
After several days of trying to get it to update properly, I finally trashed it.
My new mobo came with a PC-Cillin antivirus software disk. WOW

My OS now loads faster, the updates are 3 times faster, as well as the system scam (completes in less that 5 minutes).
Goodbye Norton...