Right click on pssetup.exe and go to properties.
Go to the compatibility tab.
Try setting compatibility to XP, and running as administrator.
Also if you installed the game in C:\Program Files\Planeshift, I would uninstall and reinstall the game somewhere else like C:\Planeshift so that you don't run into issues with UAC telling you the app can't write to C:\Program Files. That is only for Vista and Windows 7.
As for Catalyst, there was a problem that I believe was introduced with Catalyst 8.5, hence the recommendation to stay with 8.4. Others have posted they no longer have the issue with newer Catalyst releases. I run 9.3, and I don't have the problem. So I would recommend Catalyst 9.2 on XP, and 9.3 beta on Vista or Windows 7. That is just me.
Edit: Tuxide just noted in another thread that the game still crashes with VBO turned on, even with running the 9.3 drivers. So you may still need to turn off VBO.