Personally I'm using Mandriva 2010 Alpha w. 2.6.31-rc1-kernel, the open source driver works flawlessly for me. Great 2D-acceleration, great 2D IQ, video looks awesome. No 3D of course, one currently has to use the fglrx driver for that.
I use Gnome, it's possible I would encounter more problems if I used KDE4 as Kwin might not like the absent 3D-support in the open source driver. But with Gnome it's perfect and I'm very happy with my HD4350. Totally silent, HDMI + HDMI-audio and low power consumption
May I suggest you switch to Gnome and see to it that you use the open source driver?
Back in the X1xxx days, soneone issued a radeon X1050 card. It was slower than toast. I hear ATI's on-board graphics chipsets (780, 790GX) are pretty good these days, but if you want an extra card I don't think that's available in that power envelope.
i was actually rather suprised with how good the 780/3200 is.