the HD 4250 should do quite well.
I tried planeshift already on RHEL and arch linux with fglrx 10.x drivers on the following cards without major issues: HD 3200, HD 4200, HD 4830, HD 5770
I didn't try a HD 4250 myself, but as the HD 4200 works without any issues, I doubt there'll be any with a HD 4250