Larian is fairly conservative when setting the minimum system requirements; you may be able to get the game running ok on lesser systems, though obviously not as well.
Since the amount of video memory itself is not the problem, the issue may be with the specification that the video card be at least DirectX 8.1 and compatible with DirectX 9 drivers.
If you run dxdiag (click Start | Run, type in dxdiag and hit Enter), does it report any problems? There are a couple of tests under the Display tab.
If it does come to replacing your current video card, you should be able to find something more than adequate in the US$30-50 range. I wouldn't necessarily upgrade just for one game, unless you are looking for an excuse (which it doesn't sound like). However, since you started off at 640x480 in case you ran low on memory, I'm guessing that is from habit and an upgrade would help games in general.
You might also want to check your motherboard manual for the type of RAM it uses and the available slots. Windows XP takes up a good chunk of your 256MB just loading, so another 256 or 512MB RAM should give a noticeable improvement in games and other memory intensive programs. More RAM would probably be the most effective upgrade, though it would be less likely than a new video card to help get BD running.
