System Restore doesn't back up everything, likely missing the installation log used by the program to determine how, exactly, to uninstall the software. Without that you have to remove it manually. The Windows Installer Cleanup Utility can remove programs in such cases, but its scope is limited to specific types of program installations. Aside from that you can delete the appropriate folder in C:\Program Files and then use CCleaner and RegSeeker to clean up the remnants left behind.
Hope this helps,
John
P.S. Some programs, such as Symantec and McAfee security suites, also have custom uninstallers available for download in cases like this.
I've got Vista Home Edition on an hp pavilion dv6000 laptop.
When I first got the laptop I created a restore point and then I went through uninstalling programs I didn't want. I realized I'd uninstalled a program I actually did want so I restored using the restore point I had created. Then I went back to uninstall the programs I truly didn't want.
I select a program to uninstall and click on uninstall. I get an error message that the installer encountered an error and can't continue. The program is still there. Some programs will uninstall, others won't. The one program that's giving me a lot of problems had been uninstalled in that first go-round, before I restored.
Anyone else experienced this problem?

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic