I'll be critical of both ATI and Nvidia in this post. So, pay attention.
One other complaint or concern with ATI: you need decent drivers to obtain the advantage of the lower power and lower heat that the newer ATI cards provide. So, what good are these advantages if ATI/AMD cannot even offer the required support? You need good drivers for these cards to run optimally, just ask Nvidia. I told you I'd be criticizing them both in almost the same sentence.
I have read of Compiz/3D (desktop effects) being an issue in both Gnome and KDE (although, it seems more prominent a problem when using KDE 4) but in my perspective, the issues seem to crop up more in machines with ATI cards. It's the wait and the inevitable problems that causes me to hesitate buying an ATI card. If the HD 4xxx card can be bought cheaply enough I'd consider that. Otherwise, I'd go with Nvidia, maybe a GT 240 if you don't game.