First of all, there is a diffrence between 256 vs 512. E.g. without a 512mb card, you cant choose "high" textures in the latest Ghost Recon - even if you play in 640X480.
With games like Crysis coming, 512mb will be needed to fully enjoy the power of an X1800XT.
http://rage3d.com/articles/preydemoperf/
In prey, the X1600XTs in CF loose against the X1800XT in all cases (but not by much). Also shows the the kind of performance boost you can expect (just make sure to set Catalyst A.I. to 'Advanced'!).
My tip would be, if the 512mb version of the X1800XT isn´t that much more expensive - then go with a X1800XT 512mb. If it is too expensive, go with a single X1800XT 256mb to get the wanted performance boost.
However, if I had an X1600XT, i wouldn´t upgrade

I always upgrade when my hardware is below minimum. I bought my current machine in new year, and before it i had a Geforce 3 and AMD 1800+
So, if you´re going with DX10 cards, maybe waiting or just getting a cheap second X1600XT would be the way to go.