The real problem with the paradox is in the verb shave is used differently in two instances.

To demonstrate this, here is my solution to the paradox:

Those men that shave themselves do not go to the barber.

Those men that do not shave themselves are shaved by the barber. This should really be, those men that do not shave themselves are barbered by the barber.

And like that, the paradox is solved.

Does the barber shave himself? Yes, but he does not barber himself.

Alex