Hello,
this problem may be related to incorrect language constants.
Booking uses the Joomla's language constants for date/time formatting. If they are not compatible with date function format, it may cause such problems.
It should however work fine with the ones that are default in Joomla (at least for English), so please make sure you are not using some changed ones that would not be incompatible.
Also I am sure this has been already discussed here, so maybe try searching bit in history to find more about this problem.