My experience was similar to Hypathia's. I went into my local SSA office and filled out the application to get a new card, and filled in my new name and marked 'F' on the form. I only had the court order for my name change, I was still pre-op but the clerk obviously saw me as a woman. I politely asked him to change the gender marker on my record, said something to the effect that it was a "mistake" that it was listed 'M' on the record, and he said "no problem ma'am" and a few mouse clicks and I was all set! Took all of 10 mins in NY. Got my new card in the mail a month later.