I had my name changed just before my transition at work, and went to the SS office to get a new SS card that matched my new identity. I remember being told at work that they needed to make sure the information they sent to SS for wages, etc., all matched up, and there was no hassle about it. I was fortunate to transition at a university that was very supportive of me. I sent lots of faxes of the name change to credit cards, insurance, etc. to get everything in sync.
I live in VA, and went to DMV around that time to get my license changed. I had heard that they would not change the gender until post-surgery, but I had no problem when I asked for "Name and Gender Change for my Driver's License", and they took a new picture as well. I was dancing with joy in the parking lot after they gave me the license and I saw the gender maker said "F".