Have you called to ask what additional information they might accept to establish birth?

From what you've said of the message, they are not asserting you are not a US citizen. I imagine they want some corroborating evidence - perhaps a social security card, or a high-school diploma (or enrollment records before that).