Deleting an appointment...time slots not opening back up.

Having an problem...

When someone cancels or wants to reschedule their appointment, their reserved time slots are not opening back up. This was never a problem when I used this plugin in the past. Could it have something to do with them already paying their deposit through paypal?

Here is my link: http://bit.ly/14FBNDk

You can see that Wednesday, April 3rd from 1:00pm on is blocked off even though I have no appointments at all on that day.

I've tried turning the plugin caching on and off as well as Quick Cache with no luck. There must be a trick or something I'm overlooking.