That system specification reveals a lot. I would say that the only issue is expecting reasonable performance out of a video card that uses a 64-bit memory bus. It's already been proven on windows ( where the drivers have heavy optimizations). Anyways, most game developers try to target cards that have at least a 128-bit memory bus, and then as an after thought they rework things for the lower end cards. Also, I do agree that replacing the power supply is a must. Personally i would look at FSP or seasonic for power supplies, and try to keep around 500w total.
Anyways, what determines 90% of the performance is the graphics fillrates.
Anyways, I went ahead and looked at the graphics cards more, and got two groups of cards to suggest based on the card having 128-bit memory bus as a feature.
For Nvidia Graphics: 
GeForce GT 430 or higher
GeForce GT 530 or higher
GeForce GT 630 or higher
For AMD : (Dedicated cards only )
Radeon HD 5550 or higher
Radeon HD 6500 or higher
Radeon HD 7570 or higher
 Wikipedia: Comparision of Nvidia Graphics cards
Wikipedia: Comparision of AMD Graphics cards
Anyways, I only pick AMD/ATI since they offer the best features for the price generally.