The 2600xt would be the better buy, but with all the hulla-bellu over AoC not using ATi cards to it's maximum opposed to nVidia I don't know how much of an improvement you'd see.
Has your friend tried playing the game on default high and then disabling shadows, water reflection, and AF?
Worked for me and my bro's comp and he's got 2 GB of RAM, P4 3.0GHZ, and a 7600GT @ 1440 x 900. I don't know what FPS he got, but it was certainly playable (around 30 FPS) and looked great. Having the same rig but with a E6600 I got like 30-50 FPS outdoors this way. Don't ask me why it works, because I couldn't tell you but it does.
The 7600GT isn't that much better than a 6800 so it should work.