entiendo el problema...
Lo podés "solucionar" aportando siempre una fuente alternativa genérica (serif, por ejemplo), o usando las Bitstream Vera
encontré esto, quizás sirva como guía
http://www.codestyle.org/css/font-fa...xResults.shtml http://tldp.org/HOWTO/Font-HOWTO/
Luego busco en mi Slackware 10 las fuentes que trae en la instalación
Edito:
No recuerdo cuáles trae por defecto jeje ya que le instalé como 2000 fuentes más...
Sí puedo decir con seguridad que Times, Helvetica y Courier están. También están las Vera (ya que Bitstream las liberó).
Además existe un paquete Microsoft True Type core fonts:
http://corefonts.sourceforge.net/
y más información por acá:
http://en.wikipedia.org/wiki/Core_fonts_for_the_Web
En definitiva, que las fuentes se pueden distribuir siempre que sea en la forma original, por lo que quizás las distribuciones más completas las incluyan. Después de todo, no hay que olvidar que Ubuntu es una distribución minimalista, que trae muchas menos cosas que otras.
Saludos.