The best cards for Linux are NVidia you may just need a newer card. I have been using Linux for many years and have tried many graphics card combos. NVidia has good drivers that work under Linux.
Giving us your present NVidia card name number would help a lot. Also the monitor you are using.
You may also want to try Linux Mint this is a new dist based on Ubunutu and works great also your card and monitor should work out of the box.
Remember when you use Ubuntu if you have a little picture of a IO card on your panel called additional drivers this instals and sets up your NVidia card and it will require a shut down and restart to activate.