Após a instalação e configuração dos pacotes os problemas começaram: apesar dos faxes serem recebidos com sucesso, “aparentemente” todos apresentavam problemas de conexão e o arquivo não continha muito mais do que a folha de rosto e algumas linhas da página enviada.
Após vários testes e brainstorms, acabei percebendo que a versão do Hylafax que vem com o Ubuntu 10.04 (Hylafax 6.0.3) estava bugada, motivo pelo qual estava tendo tantos problemas.
Resolvi então testar uma versão mais atual do software e percebi que a versão 6.0.5 disponibilizada pelo Ubuntu 11.04 tinha as mesmas dependências da versão anterior.
Baixei os arquivos .deb da nova versão e instalei-os manualmente. Voilá, o serviço de fax ficou perfeito.
Ainda não reportei o bug mas pretendo fazê-lo nos próximos dias. Assim, enquanto não sai a correção oficial, espero que este post possa ajudar outras pessoas que estejam passando pelo mesmo problema que tive.