Accommodation in Japan

Hey people, got a few questions about accommodation in Japan.

First, for Koyasan, I would like to stay in a temple for one night. What is the best way to reserve something like this? I have been to the website, and it only gives a phone number. Is this the only way to do it? I dont mind which one I stay in, but prefereably one that has a prayer/ceremony in the morning!

Can anyone recommened a onsen ryokan that is good? I dont want to stay in one every night, but I have been told they are worth experiencing. I will be visiting the following places during June & July:
Tokyo
Kyoto
Osaka
Nara
Kanazawa
Takayama
Hiroshima
Nikko
Haokone
Kumamoto
Kagoshima

If anyone can recommened good cheap accommodation in any of these places as well, that would be great (3000-5000 yen). Obviously youth hostels are the cheapest way to do things, but if I can stay in a Ryokan or Minshuku more often for that kind of price, that would be a better experience.

Finally, for places that don't have online booking facilities or e-mail address', and the only way to reserve a place is by phone - from peoples experiences, is there usually a problem with the language barrier?

Thanks for any help that can be given.

Chris

suggestions:
1-for Tokyo and Nikko stay in Tokyo
for Kyoto, Osaka, Nara stay in either Kyoto or Osaka. these 3 towns are close to one another and easily accessible by frequent trains.
2- for 3000-5000 you will not get a decent Ryokan. You will get a small Japanese style room that may not have a bath. no meals. A decent Ryokan will cost at least Y 10 000 per person, more with meals. More still if it has a onsen.
3-check
www.japan-guide.com/e/e2025.html
for general info on accomodations in Japan
and www.japanhotel.net for business hotels and a few ryokans.
many people like reserving via http://travel.rakuten.co.jp/en/
and of course there is the very popular Toyoko inn chain see www.toyoko-inn.com/eng/
we never had problems reserving by internet.

One of the best resources for accommodation sites is the Japan National Tourist Organization (jnto) website. www.jnto.go.jp
Go to the accommodation portion and you'll find links and descriptions of many organizations that can help you make reservations. They note price ranges, if English is spoken, etc. Japan has really been enlarging and improving their tourism information and it's truly worth a look.