It's possible that you are infected by malware (not necessarily a 'virus'). You could try several online antivirus scanners, but it might make more sense to try MBAM or SAS (free version), they often catch things that antivirus programs miss.
But I suspect it's not a virus.
McAfee told you to uninstall McAfee ? My guess would be that they suggested the shortcut.
Here is a link that might help: (see post 2 by Ex Brit)
http://forums.mcafeehelp.com/showthread.php?t=226124&highlight=mcprI would remove the browsing history (you'll lose passwords and such), or at least the temporary files before trying to reinstall McAfee again. And make sure that your time/date zone is accurate.
Of course, this may not help.