You may have to configure McAfee to let NAV function normally - click here for instructions. The article applies to NAV 2003 but the principle is the same. Click on the yellow boxes in the middle of the page before 'McAfee Firewall', & at the bottom before 'Manual Configuration Information' to expand & read the instructions/info contained in them.
No you don't have overkill. You have a firewall & antivirus + ad/spyware scanners which is adequate protection these days. I'd suggest you also install SpywareBlaster - click here, which blocks most ad/spyware/diallers/scum installing on your PC (in the first place) as you surf. Good luck, G