If rescheduling is the biggest problem, this site I used to work on might help: http://hourville.com/online-scheduling/
How does it handle the rescheduling problem? It's not the "writing down the new appointment" part of rescheduling that is the problem.
People can pick their own new spot in the schedule without having to go back and forth to find available times that work for both parties. The empty bubbles can still be a problem.
I might not completely understand the problems he runs into, but I think it could help.
When someone books an appointment for Monday and then later reschedules it for Friday, a Monday booking is lost. Every time that happens you give up a booking for free.
Ah, so it's not the process, just the fact that a rescheduling happens at all. That sounds like a problem that technology can't fix.
Sure it can. Here's a simple response: you have can book an appointment for any available time slot, but you can reschedule only within a limited number of slots.
That's pretty good, but how do you distinguish a rescheduling from a new appointment? Are most customers scheduled at the same time every week for long periods of time? If so, that makes lots of sense.
That's also just one idea.
It's very easy to track which customers are rescheduling. It may be the case that a timely reminder prevents them from doing so. So that's another technological response to the problem.
Here's another: it is probably the case that rescheduling well in advance is better than rescheduling late. The earlier you reschedule the more economic value your original time slot has. So, it may be that a nudge like this gets you to free up your original spot while it's still saleable.
Those are just random thoughts off the top of my head. I just don't agree that this basic business problem admits to no technical solutions.
The biggest problem he seemed to have wasn't reminding people to show up; it was having a streamlined process for handling people rescheduling. Scheduling changes create drama for him by forcing him to renegotiate lesson times, and of course it creates bubbles in the schedule.