Uninstall Reader, try to find and use the Microsoft Installer Cleanup Tool to remove anything left over in the Registry, then re-install Reader.
I was having the exact same problems (I'm using Windows XP SP3 and IE 8) and tried all of the troubleshooting suggestions from Adobe. I also tried the suggestion from Michael, but couldn't find the Cleanup Tool. Anyway, I ended up uninstalling Adobe Reader 9.3.4 (which is what started all the problems) via Add/Remove Programs in the Control Panel. Since I didn't really know anything about the Cleanup Tool or where to find it, I went to http://get.adobe.com/reader/otherversions/ and downloaded Reader 8.2.0. Problem solved! I haven't seen this yet, but if I ever get another message prompting me to upgrade to the latest version I will decline. Hope this helps!