1. 12.10 до сих пор глюканутая, ставьте 12.04. Кстати, тогда никаких фокусов с linux-headers-generic проделывать не придётся (хотя и не факт, что дрова заработают, но в 12.04 одно от другого не зависит).
2. Установка видеодрайвера по мануалу
https://help.ubuntu.ru/wiki/установка_драйвера_ati теоретически должна исправить ситуацию. (Передварительно полностью скачайте все обновления системы.)
3. Таки надо, что бы Grub подхватывал Windows (точне её загрузчик, ибо на самом деле это именно так) или не надо, чтоб похватывал?
а) Если не надо, то ставите Ubuntu на другой физизический диск, относительно Windows, и туда же (на винчестер с Ubuntu) ставите Grub. Загружаемую систему потом выбираете по функциональной клавише быстрого приоритете загрузки или через BIOS.
б) Всё как в пункте а), но после перезагрузки зайти в Ubuntu в терминал и сделать
sudo update-grub
Теоретически Grub подхватит загрузчик Windows. Ноя сам не пробовал, так что не уверен.
Если подхватит, то результат будет не отличим от пункта в).
в) Ставите Ubuntu на другой физизический диск, относительно Windows, а загрузчик Grub на тот винчестер, где стоит Windows, и который в этот момент указан в Биос загрузочным. Ставить надо именно на устройство, а не на раздел, то есть на sda, а не на sda1, sda2 и т.п. Grub подхватит загрузчик Windows и всё заработает. Более того, при переустановке Ubuntu на любой раздел и даже другой винчестер, ставите Grab туда же, то есть на sda. По-идее, всё должно работать.