Try making a shortcut to regedit. If the shortcut doesn't work, you're PC is probably still infected.
You may have a "Rootkit" on your system. Rootkits are extremely hard to get rid of (fresh install is the current 100% solution), and they are very effective at blocking attempts to get rid of them (i.e. locking out regedit, command prompts, hiding themselves and their dependencies).
Can McAffee update itself?
Try this tool:
http://www.f-secure.com/blacklight/ It is beta, but it might be able to ID a problem.
EDIT: What virus did McAfee find? I ask, as some viruses are currently associated with Rootkits (they install, protect and spread each other).