Sou novo no Ubuntu e espero poder ajudá-lo, pois tive o mesmo problema com o Lexmark Platinum Pro 905.
Eu tenho o Ubuntu 12.4. e é assim que eu tenho a minha impressora para trabalhar.
Eu encontrei esta página link e instalei os pacotes escritor sugerido. O arquivo Lexmark é (.deb) e tem que ser instalado usando o Gerenciador de Pacotes Debian. Como não consegui encontrar o Gerenciador de Pacotes Debian, instalei o Instalador de Pacotes QApt do Ubuntu Software Center (Vá para o Ubuntu Software Center e na caixa de busca digite "deb"), então baixei o arquivo da impressora. Isso é o que eu fiz em seguida: Selecionei o arquivo, cliquei nele com o botão direito e selecionei a opção para abrir com o QApt Package Installer. Depois que o driver foi instalado, continuei adicionando uma nova impressora. Eu selecionei impressora de rede, em seguida, a partir das opções que eu selecionei o que tinha "lxhcp". Depois disso, selecionei o driver da impressora e da página de teste impressa e outros documentos sem problemas.
Felicidades!