Não tenho certeza se o que está causando o problema aqui, mas você provavelmente não quer que o padrão seja expandido pelo shell, então você deve citá-lo:
Se você tiver um arquivo fglrx-14.10.1006.1001
no diretório atual,
o comando
sudo apt-get remove --purge fglrx*
é expandido para
sudo apt-get remove --purge fglrx-14.10.1006.1001
que explicaria por que apt-get
está procurando por esse pacote.
Cite o padrão para evitar que o shell interprete o *
:
sudo apt-get remove --purge "fglrx*"