It would seem I am having the same issue. I updated to 13.1 through catalyst and my performance seems to have dropped. My system is nearly identical to yours but I am using windows 7 64bit.
We probably should have done a fresh install of 13.1 instead of updating through catalyst because we could be experiencing issues with the 2 versions crossing. So thats what I am going to go do right now.. in case you need help with the redo I'll tell you the best route.
1. Download 13.1 drivers or whatever you're going to install and if you dont have it also download Driver Cleaner Pro
2. Uninstall Catalyst and all drivers through control panel and reboot PC.
3. Open Driver Cleaner Pro and remove all ATI files using that program because 99 times out of 100 their will be left over files
4. Install 13.1 and reboot PC again and you should be good to go.