Debian squeezeのpsqlはreadlineではなくlibeditを使用しています。どうやらこれがバグ持ちのようで日本語入力できないようです。
試しに、psql -nでreadlineを使用しないオプションをつけると日本語入力が可能になります。しかしこの場合にはヒストリーとかのreadlineの機能が使えないので解決方法としてはちょっといまいち。結論はlibreadlineを使用したパッケージを作り直すしかありません。
時間はかかりますがが、今回のパッケージの作成はそれほど難易度は高くありません。