Actually, I changed my gender with Social Security just with the chest operation. What I had to do first was get a court-ordered gender change from the county. For that, I used a letter from my surgeon that said I'd had gender reassignment surgery. Then I had to change my birth certificate with that court order. Finally, I brought the birth certificate to Social Security (they let you mail it in, too, BTW) and got it changed. Whew!
So I guess you should call up your nearest county courthouse and ask them what's needed to get a court-ordered gender change. Most likely a surgery letter (it doesn't have to say the type of surgery - most don't) and then you can go from there.