Yes, if the barber was a woman we wouldn't have a problem...
But seriously..
The barber was supposed to shave all men who didn't shave themselves. There are two reasons for a man not to shave.
1. he goes to the barber
2. he wants his facial hair
We only have a paradox when the barbers reason to not shave is no 1. If it is no. 2 everything is dandy