MeAndroo, what exactly do you mean by going through an ANA special? If i could only afford going to Tokyo or Okinawa, should i go with Tokyo?
Well every so often, ANA (all nippon airways) or other airlines will join up with hotels in Okinawa to offer fantastic deals. I got a 2 night stay, all meals, transport to and from Naha airport, activity passes for the hotel (this was key) and flight for under 250 bucks. If you have a host family, they can check this out for you...just another reason to do homestay. Just so you know, though, this was what's considered the off-season (early March), so the weather wasn't spectacular, but still a decent 80 degrees and partially sunny. I went again in July, and it was MUCH more expensive.
If I had a choice between Okinawa and Tokyo, though, I'd visit Tokyo. Okinawa is beautiful and much different from the rest of Japan, but you're there to see Japan. I found it necessary to explore Tokyo just because it is the focal point of all international attention, and I wanted to see how many of the rumors were true. I spent some of my happiest days outside of Tokyo, however, and definitely recommend travel in all areas.
Also, it sounds like with what you guys did while in Japan, travel wise that you went over with a ton of cash. How much do you think one could spend on misc. expenses such as travel?
Well, there are ways to live VERY cheap on the road. With the afore-mentioned sesshun juu hachi kippu, you get 5 days of free travel on any semi-express and slower line for about 100 bucks. Great deal if you're planning on going good distances, especialy in a group. Hostels save money, as do konbini bentos. I spent way more money staying around Tokyo than I ever did traveling, in comparable time.
You COULD spend any amount of money on travel, particularly because of how the shinkansen system is set up and how much flights cost. In all liklihood, you'll want to spend as little time actually en route as possible because vacation times can be limited.