Showing (binary) availability on date picker

I'm working on a system which uses a date picker to reserve a date in the system. The specs are:

• Dates have two states: Available for booking, or not available.
• You can only book one date at a time.

My proposal to my client is to grey out all the dates which are not available, while the available ones are in solid colors. If a user was to try to click one of the unavailable dates, a tooltip would show up and let the user known.

But, the client says he/she wants to fill the date picker with colors, green and red, to signify which dates are available to pick from.

From my perspective, this will only clutter the interface and make it generally more mentally straining. However, I'm here since I would like to hear your opinions to broaden up my view.

I've attached a generic date picker (found on google image) to give you an example of what I mean.