Mr Hyde, yo no sé que puedes hacer, pero, creo que deberías preguntar en varias asociaciones y contarles ésto(lo mismo que cuentas aquí) para ver si ellos saben darte mejor respuesta que yo.
Citar:
http://www.carlaantonelli.com/Nueva-ley-transexuales-espana-guia-rapida-modelo%20solicitud-para-cambio-de-nombre-y-sexo-en-registro-civil.htm
No sé a que te refieres, yo, links sobre un tema relacionado, veo éste.
Pero no creo que sea lo que preguntas.
Igual, pienso que si dices que ha habido más problemas con respecto a este tema donde te hacen lo del cambio en el registro(pienso que deberías preguntar a alguna asociación de la zona, para ser más específicos).
Entre otras cosas por si resulta pertinente hacer una denuncia o algo, para conseguir que hagan lo que tienen que hacer.
Lo siento, por no saberte dar una mejor respuesta, hombre.
Ánimo y suerte. Igual muevete y haz algo, para ver si consigues el DNI. Y si es necesario ponte en contacto con alguna asociación. Por si te resulta útil o te dan mejores consejos que las que podamos darte las y los que estamos por el foro.