Yes, basically for FSX, you need a card wich has a LOT of memory on it. 256 Mb are far from being enough, and I guess 512 is still quite limited.
Of course, with the tweaks and the reduced autogen textures packs available for download here, you can get FSX to run quite well on a 256 Mb video card, but in that way you loose a lot of graphic quality.
If you are to upgrade your hardware, just wait a month or two. ATI is supposed to issue their first DX10 card at the end of March, and NVidia has issued their DX10 8800 card one month ago more or less, so it's still VERY expensive. Once the ATI cad reach the stores, the competition will hopefully make the prices decrease... and anyway, the DX10 patch for FSX will not be ready until at least one month... and I would bet two.
So you have time

Save your money for now, and make your upgrade for DX10.