iPhone offers very good multi language support including Japanese display and input.
If you have to stick to AT&T, I think there are virtually no alternatives.
Android phones have excellent kanji support as well as free apps for an English-Japanese translator in hiragana, katagana and kanji, and Simeji, a Japanese keyboard that works exactly like the one on a windows computer.