I think I'd resolve it by saying that any bookings made in a timezone that has changed its definition will be cancelled if the new definition causes the booking to conflict with another (including the case where two or more timezones have changed simultaneously: all involved bookings attached to changing timezones are cancelled).
"The timezone you have used to define this booking has been altered, and the booking cannot be updated due to unavailability of the resource XXXX. Please choose a new time for this booking."
It's also interesting that since this doesn't happen frequently enough it's usually hard to develop a good way to get out of it.