内容が多少重なりますが、私のところでは下記の手順で、動いています。
（印刷ジョブの処理中に「接続されていません」と表示されますが、しばらくすると、印刷されるようです。）
9.10と10.04 beta2 で確認してあります。

1) libcupsys2を下記からダウンロード＆インストール。
http://packages.ubuntu.com/ja/intrepid-updates/all/libcupsys2/download

2) c2110のドライバを下記からダウンロード＆インストール
http://www.fujixerox.co.jp/download/docuprint_c/download/2110/linux_deb/

3) マニュアル
http://download.fujixerox.co.jp/pub/exe/docuprint/c2110/ME4415J1-1.pdf
に従い、http://localhost:631 でプリンタを追加。（メーカー FX, 機種名 c2110を選択。）

4) /etc/apparmor.d/usr.sbin.cupsd の
「 # third-party printer drivers; no known structure here」
のあとあたりに、
「/usr/lib/cups/filter/FX_DocuPrint_C2110/FXM_PF Ux,」
の1行を追加。その後、
sudo /etc/init.d/apparmor reload
で apparmor を再起動。
（参考：http://islandlinux.org/howto/upgrading-ubuntu-breaks-printer-cupsys）

以上で、印刷できるようになりました。asas さんのケースですと、4) だけやれば動くかもしれません。
参考になれば幸いです。

Fuji Xerox DocuPrint C2110ではないのですが、OEMのNEC　PR-L５７５０Cでの印刷についてまねてやってみました。
1)は同様
2)ドライバを下記から取得。
http://www.nec.co.jp/products/laser/support/os/linux/download/mw5750c.html
3) マニュアル
2)と同じところからダウンロード。
4) /etc/apparmor.d/usr.sbin.cupsd の
「 # third-party printer drivers; no known structure here」
のあとあたりに、
/usr/lib/cups/filter/NEC_MultiWriter_5750C/NCM_PF Ux,
を追加

5)プリンターは、システム->システム管理->印刷で追加
で印刷出来ました。ありがとうございます。

はははは、私も安さに引かれてインクジェットから乗り換えたのですが出力出来ないのでイライラしていました。
jui205さんの書き込みでほんとに助かりました。(^^;)