Getting broadband in Japan is something of a slow process. That said, Japan is one of the most advanced countries in the world when it comes to network infrastructure. You can get much higher capacity internet connections than in most other developed countries, for the same cost.
Yahoo!BB generally takes about a month as mentioned above (although if there's a lot of demand in your area, it could be 6 weeks). First, they need to check the line to see if it supports ADSL - you may be in a modern area that is all fibre (known in Japanese as hikari cable). ADSL is designed to run over standard copper phone lines, so if you live in a fibre area, you will need B-FLETS instead.
The big bonus with B-FLETS is that it is ridiculously fast (100Mbps) compared to a maximum of 24 Mbps for the new "ADSL More II" or "ADSL More 24". (although 24mbps is probably more than you'll ever need anyway!) The downside is that B-FLETS can take 2 months or more to get installed.
Both ADSL and B-FLETS generally involved a visit to your apartment/house by an NTT engineer, who may not speak English, so it's a good idea to have a Japanese friend around. You'll probably also get half a dozen phone calls from NTT and the ISP.
One company worth checking out is JENS Spinnet:
SpinNet is an Internet Service Provider in Japan owned by Softbank and we offer English support.
www.spinnet.jp
They have full English language support and will even talk you through setting up the broadband modem etc over the phone. They also have a reputation for providing very fast connections. (You may have a very fast line into your house, but the real capacity still depends on your ISP).
There are ways to get your phone line for a lot less than 72,000. I'd suggest you get a Japanese friend to do an online application for you (unless you can read Japanese yourself). I did my application online when I moved apartment recently and I think the total cost was about 5,000. Go to the NTT East website and follow the links.
Finally, if you want to go mobile, I'd definitely recommend getting an AU phone instead of DoCoMo (forget J-Phone - they don't offer a data service). AU supports 144kbps straight out of the box (about 2 and a half times the speed of most standard modems). The only slight drawback with them is that they have a relatively limited number of bi-lingual handsets - but if you want it mainly for data, then this isn't so much of an issue).
Hope this helps.
Tiger