Acabei de encontrar exatamente o mesmo problema em 14.04.2 depois de alternar entre os drivers de vídeo de código aberto e fechado. Por alguma razão, a limpeza do apt-get não ajudou, mas remover manualmente os arquivos ofensivos resolveu o problema.
Em /etc/ , você encontrará as pastas ati/ e ati.dpkg-bak/ . Faça o backup de ati/ para ati.bak ou algo assim e remova os dois ati/ e ati.dpkg-bak/ . Depois disso, vá para /var/cache/apt/archives/ e rm the fglrx deb.
Agora, tente novamente sudo apt-get install fglrx . Deve apenas funcionar.