To anyone going to Japan who is reluctant to use AirBnB but still does not want to stay in an "ordinary" hotel, I can recommend going to a Ryokan:

http://en.wikipedia.org/wiki/Ryokan_%28inn%29

Ryokans are Japenese guest houses and can be found in many cities around the country. I once stayed in one close to the Hongo campus of the University and had a fantastic experience. Sleeping in a traditional Japenese room and waking up to a traditional Japanese breakfast before going to the bathhouse or having a walk in the garden is just awesome, even more so because you can do this while being in the center of a city with 11 million inhabitants :D

http://www.tripadvisor.com/Hotel_Review-g1066442-d320548-Rev...