I would try removing the program via the standard add/remove programs dialog as the above posted already detailed..
1. Select Start > Settings > Control Panel.
2. Open the Add or Remove Programs panel.
3. Select Adobe AIR to remove the runtime.
4. Click the Change/Remove button.
If you're on Vista or Windows 7, the steps may vary slightly but it should be pretty much the same.
Your other option is brute-forcing the removal and scrubbing any trace of Adobe AIR from your system and registry. It's a pretty effective utility in diagnosing broken programs and removing those stubborn broken uninstallers. If all else, remove it with the perfect uninstaller utility. It's a paid product but it's worth the one-time fee. You can put it on three systems at a time, and use it forever. I had to download it last week when my Adobe Photoshop started crashing and I couldn't uninstall it. I spent hours trying to uninstall manually then just broke down and used the utility and it took literally seconds. lol, I couldn't believe it.
I would probably try a bit more free before I tried any paid etc.
It would help if you could describe what happens when you try to uninstall Adobe AIR. Do you get any error messages?
You can also try Windows Installer Cleanup Utility. A post here that's a bit data describes using it to remove AIR and an AIR application (twhirl) but the directions could apply to any AIR application + runtime: http://www.zoliblog.com/tag/adobe-air/
Windows Installer Cleanup Utility: http://support.microsoft.com/kb/290301
hope that helps.