The OED seems to express that it was not so much who barbarians were, but who they were not. They were not Greek.
There is probably a tie-in that the northern coast of Africa was known as the Barbary States.