What did your parents use to get your passport in the first place? Did they get a Report of Birth Abroad at the embassy? If so you can use that. There's also a process to apply for a citizenship certificate from USCIS, but you will probably want a lawyer for that.
They were able to use their birth certificates and my old, handwritten foreign birth certificate at the time.
They didn't report the birth to the state department since it was just over the border. There's thousands of people from S Texas with similar problems I've read.
[edit] Also, the USCIS N600 requires a birth certificate as well, so that's why I didn't consider it.
That's right, there are alternative avenues to getting a certificate of citizenship or passport (although they require a good bit of information and documentation).
