I think I was reading a benchmark article over at tomshardware a few weeks ago about memory size for video cards.  To sum it up, unless you're running really high monitor resolutions over 1080p or higher, 512-768 cards run everything just fine.
What are these 'problems' you're running into?  Are you sure its the video card's fault and not something else?  Drivers? Other hardware? etc?