I think Japanese phones are different; they have they're own system, sort of, that only works in Japan. My cousins in asia can use their nokias in almost anywhere they travel within asia though, but when i brought my phone to asia i couldn't use it at all (except for "emergency calls").
I think you're pretty much going to have to get an unlocked phone. My cousin (in the philippines) got a phone from hong kong and just needed a SIM card though. I dunno if this'll help you:
http://euc.jp/misc/cellphones.en.html
"Japanese Cellular Phone FAQ"
But i do agree with you, our phones are the pits LOL it's getting better though.