Eu encontrei este link que resolveu o problema para mim. Em resumo:
Desde Natty (11.04), o Ubuntu irá montar sua partição root como somente leitura, então você não pode fazer alterações imediatamente ... Para obter Read Write, você precisa executar isso no shell do root:
mount -o remount, rw /
Os comandos apt-get funcionaram para mim depois disso. Eu corri apt-get remove fglrx*
e depois de reiniciar os drivers de código aberto estão sendo usados.