There may be some remnants of McAfee left behind (it could be registry legacy keys, etc.), I believe there is a manual removal tool/instructions on their web site.
Also both AdAware and Spybot S&D have resident elements (if user activated), AdWatch (if you have the paid for AdAware) and TeaTimer with Spybot S&D. These can block the creation of startup entries, if they are present in your system disable them and try to reinstall again following Tech's list.
If it won't let you uninstall (possibly because of a failed install), download and use the uninstall utility.