O link da Orestis é realmente ótimo.
Em suma, o motivo dos seus problemas pode ser de 64 bits. Os drivers da Xerox para Phaser 3100MFP são de 32 bits e é por isso que você precisará instalar algumas bibliotecas de 32 bits.
Primeiro, baixe o driver do site oficial da Xerox. Ele terá um arquivo de instalação para instalar o driver no banco de dados do Ubuntu. Desembale e instale-o. Pode ser necessário executar com o sudo assim:
sudo ./setup
Esta ação pode ter um problema porque é necessário ter o libjpeg62: i386 instalado. então corra antes disso:
sudo apt-get install libjpeg62:i386
Portanto, agora, se você pesquisar por drivers em Impressoras, ele será apropriado, mas ainda não funcionará, pois há algumas bibliotecas de 32 bits ausentes. Quanto ao que eu sei, o Ubuntu está usando o CUPS, então para descobrir quais bibliotecas são necessárias, execute isto:
readelf -d /usr/lib/cups/filter/rastertoprinterbin
A saída será algo assim:
Tag Type Name/Value
0x00000001 (NEEDED) Shared library: [libcupsimage.so.2]
0x00000001 (NEEDED) Shared library: [libstdc++.so.6]
0x00000001 (NEEDED) Shared library: [libm.so.6]
0x00000001 (NEEDED) Shared library: [libgcc_s.so.1]
0x00000001 (NEEDED) Shared library: [libc.so.6]
0x00000001 (NEEDED) Shared library: [libcups.so.2]
Portanto, as bibliotecas que possuem o tipo 'necessário' precisam ser instaladas. Por exemplo, para resolver lipcupsimage.so.2 você precisa instalar 'libcupsimage2: i386' (': i386' - significa sistema de 32 bits, não se esqueça de incluí-lo). O comando ficará assim:
sudo apt-get install libcupsimage:i386
Depois disso, deve funcionar bem. Eu tive o mesmo problema com a minha impressora Xerox Phaser 3100MFP - resolveu depois que eu instalei apenas 'libcupsimage'.