First off you might download Reg Cleaner if you don't have it - here :
http://www.tucows.com/preview/355220.html
There may be traces of the deleted software remaining that are somehow causing you problems. Reg. Cleaner is FREE so you might run it and go through the various processes.
What happens if you right click on the desktop > and click 'Properties' ? Do you get the interface with the 'Appearance' and 'Screensaver' settings ? If you click screensaver - there should be a few default options to choose from.
As a matter of fact the issue you describe sounds like it might be your desktop wallpaper - so try clicking Desktop and Themes on the above mentioned interface. Again select from the defaults avaliable.
As a last resort you might try reinstalling your graphics drivers - if you don't still have the driver cd, either do a Google for ' xx card driver download' - or post back here with the type card and someone may be able to supply you with a link.
---------------------------
As an aside, you might go here :
http://www.belarc.com
Get Belarc Advisor - its another freebuie that will give you a complete breakdown of your pc specs - components, software installed, etc.