O, after reading the guide, it's not 03 for all places, only tokyo.
For places like osaka (大阪), you'd dial 06 (075 for kyoto (京都), etc). It's different for every city. So if you're going to put 03 at the beginning of your phone number, you have to pick tokyo. (Just like if how you have to dial an area code if you're calling out of your area in the US.)
Here's a lis of dialing codes: http://www.i-tel.com/jcodes1e.html
Edit: If it fails after you try to confirm on the second page, try using real japanese names (You know, the ones with the chinese looking characters in them. (e.g. 中山 保井 (nakayama yasui))