Cate, I don't know the answer to your question, but I can appreciate that it would be a bit shocking to get that kind of news. That seems to me like a strange response to get from a government agency or vital records repository when someone tries to obtain a copy of his/her own birth certificate. Was any rationale offered? Were they not satisfied that you were who you claimed to be, or was it just that the information you provided did not all track with their records? Was there any explanation of what sort of documentation might be necessary to obtain your birth record? I'm also curious as to whether there is any law or written policy behind the response, or if you made the request in person, perhaps it was just a clerk winging it?
If you are certain about the date and place of birth, I think I would find a newspaper repository that may publish birth announcements, or perhaps even hospital admissions and discharges. I would also check with the hospital to see whether they maintain any applicable records. And I think I would visit vital records in person with whatever data I have and try to get a satisfactory explanation of what is needed to proceed.
I think you would also be a good candidate for a DNA test, but don't expect any instant gratification from it. Good luck!
