The easiest fix involves downloading Microsoft's free "Windows Install Clean-Up" utility, running that, select any entries for "Adobe AIR" in the list of programs and remove them. That should fix it.
To download, visit http://support.microsoft.com/kb/290301, then scroll down till you see download link.
Alternatively, Adobe suggests uninstalling via the command line when the option to uninstall AIR via Add/Remove programs is unavailable. This basically involves downloading a fresh version of AIR from their website, opening a command line (via Start > Run > cmd) then typing "AdobeAIRInstaller.exe -uninstall" (without the quotes). This presumes that you are in the directory that the AdobeAIRInstaller.exe is located in, of course.
However, the second method didn't work for me. Somehow, AIR had become corrupted and couldn't be updated or removed via traditional methods. Only the Windows Install Clean-Up utility worked.
Hope that helps!
P.S. (Someone else suggested to find Adobe Integrated Runtime in the installer clean up list and to click remove that, that it worked for them. Personally, I didn't see Integrated Runtime in the installer clean up list. For me, the problem was fixed by just removing the Adobe AIR entries.)