Man, that is hard. I am going to be facing the same thing pretty soon. Changed my name first, told them that I just really hated my first name, and preferred Sam. Then I cut my hair. As people start using the new name the stubborn hangers on started feeling uncomfortable and obvious. When they heard other people using the right name, they would just have to feel it out. I won't change pronouns for quite a while, and hopefully the t will start making changes and it will start to feel more... Natural? for people to use the right pronoun than the old one.
Although I am sure some people will be assy about it.
If you have kind co workers who would be will to use the right words and name around your stubborn people, maybe they will also pick up on the right way to do things?