It's all a matter of opinion. With today's graphic intense games, you're probably going to need at least 256 mb. There is also the matter of is it GDDR2 or 3.
As mentioned above, it's more an issue of speed than quantity... 256M is typcially more than enough for today's games, but I'd take a fast GPU with 128M over a slow one with 512M anyday...