Ubuntuがどんなmailx使ってるか知らないけど、http://sf.net/projects/heirloomから落としてコンパイルしたのは日本語表示出来たよ。