Con Ubuntu 10.04, 9,04 e 8.04, sempre versioni server, non ho mai avuto problemi.
Segui la mia guida che trovi nelle pilloline (e' un documento in pdf da scaricare dal mio sito).
http://www.lovisolo.com/hylafax/howto-hylafax.pdf

Installa anche imagemagick e libtiffopengl