Thanks for all the advice. I need to go out to Yokota AB the day after I arrive so I will just go to Vodaphone there.
Again under SOFA status you should be able to get a phone, and I wouldn't limit myself to just visiting Vodaphone. I would see what your colleagues are using, and I'm sure there is somesort of information/liason officer that assist everyone with setting up telephone/internet etc services.