「gfxboot-dev」パッケージをインストールしてみて下さい。
こちらの環境ではこれで上手く出来るようになりました。

どうやらgfxbootがバージョンアップした際に、通常パッケージと開発用パッケージに分離したようですね。
いままでgfxbootに入っていた「mkbootmsg」は「gfxboot-compile」となり、devパッケージに移ったということでしょう。多分。

バージョンアップ前にリリースされたuck2.2.1のdebパッケージは「gfxboot-dev」を知らず、「gfxboot」のみを依存パッケージとしてインストール。devパッケージは無視された。ということではないでしょうか。(憶測ですが…)

公式サイトを覗いてみると・・・いつの間にか2.4.0にバージョンアップしてますね。
変更点を確認してみると、
* gfxboot-dev dep added for maverick
がリストに入ってます。
やはりこれが原因だったのでしょうか。
他にもかなりの変更点がある模様。まだ問題があるようなら、こちらのバージョンを試してみるのも良いかも。