Eu encontrei algum artigo onde dizem que os drivers para M2XX funcionam perfeitamente mesmo para o M3XX. De qualquer forma, ter a mesma placa tentou
sudo apt-get install fglrx-updates
e comecei a trabalhar.
Outros métodos, incluindo o download de pacotes deb do link não estavam funcionando para mim, tentei pacotes fglrx-core ( 80MB cca) junto com fglrx (50MB cca) e tela preta após a reinicialização. Eu acho que pode haver alguma solução para este método também.