У меня была такая же проблема (Ubuntu 12.04, Ati 6450, драйверы галлия). Игра теперь работает, после установки этой библиотеки:
sudo apt-get install libtxc-dxtn-s2tc0