What data controller is that?
Very few of them have a valid ground to process your birh date. Do they need it to provide you the service? No? Then they fail the data minimization requirement.
and refusing access right on the ground of the birth day, which they should not have in the first place, is the cherry on the cake.
Send them a letter to tell thel that you are ready to submit a complaint to your regulator (or the lead regulatior), but that you are ready to compromize to save hassle to everybody. A few thousands are always welcome.
But again, this is valid only if the controller have no ground to process birth date. If it provide adult stuff, or legal benefits, etc. it's a different story.