Yes, it could be a virus.
Could be that, when you uninstalled, not everything was removed. This happens a lot. Most programs leave a few things behind.
It could be as simple as a leftover Preferences file trying to load a brush set that you'd added, but is now unavailable.
Here is an article that explains everything you need to know about the Preferences file and how to deal with it -
http://www.creativepro.com/story/feature/17478.html .
Another method is to hold down the CRTL-ALT-SHIFT keys when you click to start Photoshop. You should see a dialog appear asking if you want to delete the settings. Click Yes and see if it starts up.