To Diagnose and Fix installation problems automatically, please see the new Microsoft tool for this here:
For more information on the Autodesk KB Support article concerning the clean uninstall of Autodesk products, see this link:
For all other installation problems consider using the Microsoft Installer Clean Up Utility. For more information on this program, please my forum post here:
I went through all the possible guides and even tried to install cleaner to get rid of any hidden registries and so on, which did NOT help me... but after an hour of trying I found out the maya install file (not the package installer called setup.exe) And after running this file it will ask you what to do with the Maya on your PC (and yes I deleted all the folders/regs/shortucts/user datas/app datas and so on before that and I still had the problems) and then you select Uninstall and it will do all the work for you. This fixed my issue and I was able to reinstall Maya after that with the usual setup.exe The destination of the maya(only) installer is C:\Autodesk\Maya_2013_CEJ_Win_64-bit\x64\Maya or where ever you have extracted the Autodesk install files beforehand.. your folder should be as well named Maya_2013_CEJ_Win_64-bit or something very close to this. and then you go x64/Maya and select the install file in order to uninstall the program from your PC.
I know my response is a bit too late, but this might help others or you if you are still having problems doing it.
Access a broad range of knowledge to help get the most out of your products and services.