What brand/model video card do you have? Have the latest drivers installed?
Make sure you're setting Direct3D AA and not OpenGL.
Right click desktop > properties > Settings > advanced > (For ATI cards) Advanced 3D tab > Full Screen Anti Aliasing...
Amount of vidmem required varies directly with resolution and amount of AA. I think the max AA at 1280x1024 is only 6x, while the max at 1024x768 is 8x.
Dunno about your system, but give it a whirl. If it chokes, tune it down a notch.