2 weeks from Sasebo to Tokyo

We're just beginning the process of planning a trip, trekking from Sasebo in Kyushu to Tokyo, last week of March to first week of April. The plan right now only includes:

1) Travel primarily by rail
2) Visit sites to view the blossoms, including Kyoto and Tokyo specifically
3) Mt. Fuji
4) Stay in ryokan and possibly love-hotels to keep costs low

I'm a US national, and can take advantage of various deals like the rail-pass. She however is USN stationed in Sasebo, and as such cant gain access to the Rail Pass, etc, but may have access to some Military benefits we aren't aware of.

What we are looking for at this point is suggestions on how to keep the trip below 5000-6000 USD for the two of us (not including my airfare), how to best deal with the fact she wont be traveling as a "Temporary Visitor", if there are any lesser known spots across japan to visit for blossom viewing, and anything else we could do on a budget to really see Japan, not just be a tourist.

One of the biggest things we are trying to understand is if there are any US military discounts for travel in Japan that I can accompany her along with (they have several for service-members to help them learn about local culture).

Ive even considered Couch Surfing, though she's against the idea. The one thing about it I would still like to try and do is meet folks (nationals and ex-patriots alike) as we travel who'd be willing to show us some of the local things we might miss as someone passing through.

Suggestions, advice, and tips welcomed!

The rail pass isn't that great of a cost advantage compared to other travel methods.

For example, you could travel from Sasebo to Tokyo by taking inexpensive highway buses along the way and then fly back to Sasebo with a discount air ticket (can be 10,000 yen from Tokyo to Fukuoka by Skymark Airline or even less).

I recommend Iwakuni and Hiroshima as other good sakura locations along the way, although, late March could be a little bit early to see the trees in full bloom. But that depends on the weather this year, which is hard to predict.

Other tips for budget travel:
http://www.japan-guide.com/e/e2028.html

4) Stay in ryokan and possibly love-hotels to keep costs low

I agree about "love hotels," but actually "ryokan" means traditional Japanese inns (normally with hot spring and dinner/breakfast served in your room), and is something that is originally expensive. Some inexpensive hostels/small family-run inns use the word "ryokan" in their English names, thus the misunderstanding, I suppose.

So if you happen to walk into travel information desk and ask for recommendations on inexpensive accommodation, please do not ask for "ryokan" (you will end up with something expensive), but instead ask for "business hotel" or "hostel." :)

That would explain the vast difference in prices I found. I will have to look, but i had been looking at a site proclaiming to be an inn network. Most of them were in the 12,000 / night range (for 2 in a room), no private baths, meals extra and not in the room, and mainly ''japanese'' style rooms, with perhaps 1 or 2 western rooms (I was looking forward to the japanese rooms, personaly). On the other side of the coin were the inns likked to from such places as the main tourism site which was far, far more expensive, featured hot springs, and private meals.

please have a look at www.japanhotel.net they have both ryokans and business hotels,from cheap to moderate.
I usually stay at the Toyoko Inn. twins around yen 8500 (10 000 in Tokyo) they have free Japanese breakfast, washing machines etc. www.toyoko-inn.com/eng/