It looks like his pain point was that he was walking to a computer. Perhaps having a tablet by his phone could fix this problem? It could be as easy as the paper calendar solution, but since it's all being done electronically, you could allow people to schedule appointments online and such.
But why is the default assumption that the barber needs software, and we must prove out that he doesn't? The barber just wants to note some info and get on with things.
With that said, given that the barber in question has tried 10 different scheduling packages, it would seem that he is looking for something better than paper. That says to me that something is needed in his business, and that may very well be software, though the platform on which to run that software is probably not a PC with standard peripherals.
Or for that matter why not some kind of automated voice recognition system that extracts the customers schedule date directly from the phone call?