似たような例で、プリンタ名がちがいますが、
http://ubuntuforums.org/showthread.php?t=1745833
の#9ではいかがですか。

Debian4.1はOKで、3.1は要インストール。なぜかUbuntu11.043.1に戻ってしまった感がありますね。
私の場合はiP7100を使っていますが、キャノンのドライバーでなく、OpenPrintingの8600用ドライバーを流用していますので、8.04以来変更なく使えています。

http://opfc.sourceforge.jp/debian.html.ja
上記リンクはDebian用のものですので、実行しないでください。
既に行なってしまい更にアップデートまでしてしまった場合はUbuntuのシステムが破壊されてしまっている可能性が高いのでシステムを再インストールしてください。


Ubuntuの「gs-esp」パッケージが無くなった明確な理由はわかりませんが、「/usr/share/doc/ghostscript/NEWS.Debian.gz」を見ると、バージョン8.60以降のGhostscriptにはESP Ghostscriptの機能がマージされていて、OpenPrintingにも対応しているように見受けられます（英語は読めないので間違っていたら訂正をお願いします）。
で、UbuntuのGhostscriptのバージョンを「Ubuntu Packages Search」で確認すると、Ubuntuではかなり前からマージされたものが提供されているようで（参照）、「gs-esp」パッケージもそのバージョン以降、移行用のダミーパッケージとなっていたようです（参照）。
そして、キャノンのページを見ると現在では「Ubuntu 9.10まで対応」となっているようですので、あまり行儀はよくないのですが、「gs-esp」パッケージをバージョン違いのUbuntuから引っ張ってきてインストールすれば暫定的な解決法となるのではないかと思います。（Ubuntu 11.04のGhostscriptのバージョンが9系にアップされているのが気がかりではありますが、mightymouseさんがリンク先の指示通りに行ったのであれ「gs-esp」がインストールされたことで使えるようになったということのようなので、それに期待しています。また、Debianのパッケージを入れてしまう行為よりはマシだろうと思います）

ただし、キャノンのサイトにもありますように、Ubuntu 11.04は現在は未対応ですのでその辺りの配慮は必要となります。