That sounds goofy to me, Diane. Unless rules have changed quite a bit since 1999 (which is certainly possible), I changed my name and gender both at my local social security office with nothing more than the court order issued by Los Angeles Superior Court. I simply filled out the form and handed over a certified copy of the court order. No eyebrows were raised. No questions were asked. Within minutes the deed was done.
If you have options where you live, you might consider trying a different Social Security Office. Sometimes the resistance we meet when dealing with petty bureaucrates has more to do with the attitude problems of the individual than with the system, per se.
Best of luck with it.
Miharu