Other cell phone advertisers in Lighthouse and other free Japanese
publications often say they can do Japanese on US phones. Also, see any
Japanese cell phone dealer.
---
Biggest problem is that most Japanese cell phones won't run in the USA
networks and vice versa. As such, you'll either need a multi-band cell
phone capable of going on the USA network (but still having the problem
of whether they can handle japanese characters sent through the US
networks) - expensive; or a US cell phone - amazon.com, cheap.
If you have any cell phone that can go online to a web site that'll
translate alpha input into hiragana/katakana/kanji, that's another way
to go. You'll be offloading the kanji input to the website, thus you
won't care if the cell phone itself supports kanji or not - just the
website needs to. Example of this is the Treo 600 with full web
browsing capability.