I probably should have read the rest of the thread.
But yeah, make sure all traces are gone, and re-install.
...if you're installing a not-so-legit version on Photoshop, that may be your issue, Adobe's tricky with their anti-pirating stuff sometimes.
Adobe tends to connect to the internet without telling you, and might shut you down if it learns that you're not using a legit copy. (in before Roph tells me otherwise)
When did you first install this program?
Did you update it since?
Have you installed anything new, since? Like fonts, new brush sets, or anything else that could possibly interfere with Photoshop?
(Also, why not just get CS4? lol)