The cleanup tool creates log files in your %temp% directory named cleanup*.log.  Can you check and see if you have these log files so we can see what it has tried to uninstall?

Also, can you please provide specific details about which setup package you are having trouble getting to install (or uninstall) and what error messages you are receiving?