NAV does fail if you use System Restore or after certain updates. http://reviews.cnet.com/4505-3514_7-30521466.html gives it a less than stellar 71% thumbs down.
Try another antivirus if Symantec doesn't fix this for you.
I tried installing NAV 2004 on a old laptop running ME. NAV installed without prompting for a product key, but wouldn't work. I reinstalled ME from the oem recovery cd and reinstalled NAV... worked like a charm.
After updating ME, NAV won't open again. Its running with auto-protect enabled and I can change the configuration, but it won't open to manually run a scan or manually update.
Any thoughts on what might be the problem?