Couple of things come to mind.
How did you uninstall the AV? Did you use the uninstaller that came with the package? Did you use the Add/Remove Software in the Control Panel? Did you just delete directories?
A previous install/uninstall did not complete normally. Most Microsoft products will inform you of this situation and either tell you to boot or roll back the previous install.
Your installer is corrupt. You can get a new one at:
http://support.microsoft.com/?kbid=884016Installing a new installer could be problematic however, since that's the very problem you're having.
Let us know about the AV. You may have to delete all references in the registry manually.