I am running Debian Wheezy (which Ubuntu 12.04 is based on) on my desktop (with a Saphire Radeon HD 5770). I also had problems with AMD's proprietary fglrx driver. It stopped working when I upgraded from xserver 1.11 to 1.12, before Wheezy stablized (Ubuntu 12.04 is using the latest xserver 1.12 package, the same as Wheezy). Downgrading xserver to the version in Squeeze works, but isn't an ideal solution and can break other packages, such as gnome-shell.
My solution has been to use the open-source radeon driver that is included in the Linux kernel. I was surprised to discover that it works exceptionally well with my Radeon HD 5770. Although they share much of the same underlying technology, such as Gallium 3D, the radeon driver is in a very advanced state compared to the nouveau driver (the open-source nVidia driver). I have not had any problems with the radeon driver in the ~6 months since I switched from the proprietary one. I get descent framerate and graphics acceleration in GNOME 3, Minecraft, VLC, and basically everything else.
Unlike with the proprietary AMD and nVidia graphics drivers, however, you will need to install a couple of packages to get the open-source radeon driver to perform decently. It is usable without most of these packages, but I don't recommend it.
sudo apt-get install libdrm-radeon1 libdrm2 xserver-xorg-video-radeon libgl1-mesa-glx libgl1-mesa-experimental
Most of these packages are installed by default in Ubuntu 12.04, but I decided to list the essentials anyway. The libgl1-mesa-experimental package is a notable exception. It absolutely will not be installed by default, but is very useful. Don't be scared away by the 'experimental' label: it is, in fact, very stable. And installing it will drastically improve your graphics performance. I noticed the improvement most when my Minecraft framerate went up, but it is noticeable in other areas as well, such as effects rendering in GNOME 3.
If you are indeed set on buying a new nVidia graphics card to use in Linux, you will need the proprietary driver to make full use of your card. The developers of nouveau have done an excellent job reverse-engineering the kludge that is nVidia's proprietary driver, but it is in severely worse condition than the radeon or intel open-source graphics drivers because nVidia provides no assistance, unlike AMD and Intel.