Имхо (что я бы сделал).
sudo apt-get install synaptic
в синаптике в настройках источников программ (погуглите) поубирать неубунтовские ppa, если вы их ставили (xorg-edge или фиг его знает что тут народ советует). После этого там же в синаптике найти nvidia-current-updates и установить. После этого надо перезагрузиться и пробовать играть.
Если переустанавливать, то, ИМХО, ставить 13.10 32-bit. Стим 32-битный, куча игр только под 32-бита, и случайных проблем с графическими библиотеками меньше. Дальше на чистую Ubuntu ставить родной драйвер. Надо пробовать 13.10. Я сидел на убунте с 11.10 до 13.04. Новые релизы быстрее и удобнее чем 12.04