When you installed your saved files from the backup did you also install CS4 from that or did you install from the PS CS4 disk?
If you ran from the backup I think the install was botched.
What I would do is deactivate CS4. Choose to deactivate as if your installing onto another computer. Then remove CS4 and re-install. Reinstall the software as Admin. When you insert the disk don't run it. Open to explore and look for the photoshop file. in that file look for the .exe file. Right click on that and choose run as Admin.
But before you install you want to run the CS4 clean script. Follow the instructions but there is a level one or level two cleaning. Type in 3 and clean it out.
http://www.adobe.com/support/contact/cs4clean.html
Run the microsoft cleanup utility
http://support.microsoft.com/kb/290301
Download and run CCleaner to locate and remove any lingering files. It is free and works great
http://www.ccleaner.com/
If you have Adobe reader installed remove it. Sometimes it causes CS4 install issues.
Turn off any anti-virus software.
If running Vista or Windows 7 turn off Windows defender. You can keep the firewall on.
When installing CS4 you do not have to install CS3 or CS2. Just type in CS2 or CS3 serial numbers when asked.
During CS4 install at 90 percent the install will hang for about 10 mins. That is normal.
After CS4 is installed reboot. After reboot right click on PS CS4 in Start where the programs are listed. click on properties, compatibility, then check run as Admin. hit apply then ok to close. Start Photoshop and update.
If you can defrag before and after CS4 install.