How is the language barrier in Japan?

In other words, as a Native english speaker with no Japanese language experience at all, how hard is it to communicate and generally get around in pretty much anywhere in Japan. But if I have to be specific, lets say Tokyo.

If you mean for tourists, not much difficulty. You can get around alright, particularly in big cities like Tokyo (less so in rural areas, of course). Nowadays signs at train stations, etc. include English, and staff at information desks or stations can answer in English to some extent.

Getting around is no problem. I would suggest deciding where you want to go, how you're going to get there, and where you're going to stay well in advance. Use the Hyperdia website to plan your travel if you are using the train system. Even then, plan on getting on the wrong train several times during your trip.

As far as communication goes, it can be a pain at times, even if you know quite a few phrases. I would suggest "Yokushitsu ha doko ni aru ka?" (Where are the bathrooms?) and "Biru ippon ongaishimasu." (One beer, please). Having a Japanese-English phrase book would be useful, also. However, even knowing quite a few phrases and having a phrase book, communications can be somewhat challenging. But then, that's half the fun of traveling in Japan.

Yes, for travellers a phrase book would help.

"Yokushitsu ha doko ni aru ka?" (Where are the bathrooms?)

...is not quite right, Paul. "yokushitsu" is "bath-room" as in where you take a bath/shower :) So if you are looking for a toilet/washroom out on town, the right word is "senmenjo" (wash room) or even "toire" (toilet). Also it sounds nicer in polite form, so I would suggest:
- Toire wa doko ni arimasu ka?
- Senmenjo wa doko ni arimasu ka?

The shortest would be:
- Toire wa doko desu ka?

----as a Native english speaker with no Japanese language experience at all, how hard is it to communicate and generally get around in pretty much anywhere in Japan. ..Tokyo.----

Tokyo may appear suprisingly gigantic place to get around unless you are from similar places.
People in Japan are polite and help you in anyway they can but people like to move and walk fast in Tokyo as in any other big cities around Japan. Tokyo consists of diverseness in people, languages, and cultures.
It would help to be with other people to get around and stay at international hotels.

I don't speak Japanese-shame on me-- but being very familiar with Paris and London I have no problems navigating very crowded subways, streets etc. I even find Tokyo subway and the JR trains easier to use than the above European ones. There is also enough English signs to find one's way around.

You're right, that is the phrase I was trying to remember. I couldn't quite remember it.

As far as Tokyo goes, I had no problems getting around it. I tended to get on the wrong trains when I went outside Tokyo. My biggest problem was getting on trains that didn't quite go all the way to where I wanted to go. End of the line, so to speak. We just got off and waited for the next train.

Paul, didn't you checked the train route beforehand on www.hyperdia.com? you can also Google most lines..

We went in the summer and go back in a week. Its harder than you'd think. I struggled ordering Disney tickets, I even managed to order McDonalds wrong. I pointed and said number 2. she put her fingers up and said like 2, i said yeah, then i had 2 numbers 2 meals hahaha

Its funny though, but a slight challenge

Paul, didn't you checked the train route beforehand on www.hyperdia.com? you can also Google most lines..

Oh, yeah, I had our itineraries all mapped out and it seemed like it would be so easy. I forgot how hard it would be to get the other 5 people in our group to stay on my schedule. (you know, 24 year olds taking their dear old time getting ready in the morning). We ended up taking the next available train. It really didn't matter since we were only on a time schedule on two days. The rest of the time we were able to just wing it. In reality, it was quite interesting.

I lived in Tokyo for 18 months and didn't speak Japanese. I was surprised that it wasn't too difficult to get around. Signs in the train/subway platforms are in Japanese and English. Not all of the train cars have English, but if you pay attention, and listen to the operator, you will find the right station to get off.

I would also recommend planning your route in advance with hyperdia and getting a sucia card so you don't always have to stop and buy tickets. The maps at the ticket gates aren't in English. A good plan is to stay on the JR trains as much as possible and then switch to the Metro.

In terms of eating, I stuck to the restaurants with either tickets or menus with pictures. Any major hub (Shinjuku, Shibuya, Ueno,etc.,) will have tons of places to eat.

But, it takes patience. Tokyo is always crowded: crowded, pretty crowded, oh my god, and panic attack. Try to avoid the trains on the rush hours!