I thought it had something to do with the Romans' being clean-shaven. They equated these tribes with bearded men -- hence, the word "barbe."
I also heard that the word may have originated from Greek, as well. The xenophobic Greeks equated beards with foreigners.
One point wrong, Allen -- The English term “barbarian” is derived from the Greek barbaros, Latinized as barbarus.
The rest of what you wrote is correct
Moochpooch, it had nothing to be done with beards - the Greeks were big on their beards, it was a Latin thing to go clean-shaven (as then when you fought, your opponent had nothing to grab on)
This is similar to the Polish (and to a large extent Slavic) terms:
for Germans - Niemcy - basically from "mute" i.e. people who can't speak clearly
Wloch - Italians - the origin is from the German term Wallach meaning Italic speaking non-German and was the term for the Britons (hence Wales/Welsh), French (Wallons/Wallonia), Romanians (Vlachs, Wallachia)