I've done that myself, halfway through a 10 year run with a big company. It worked perfectly fine, though not instantly.
Sure, it's very important to you (and me at the time). It is, literally self-important.
Nobody has any problem with that. However, to them, it is a very small part of their day, and an ingrained habit to break. They don't wish to offend, but they would think it unfair if they were harshly judged for an honest mistake.
So you have to be the picture of patience on the matter. When you hear the wrong name, you need to let it slide 99.9% of the time, and be gracious about it.
The problem is, if you kick up a fuss about it, then you create an impression you really do not want - of vanity, a highly disrespected trait. Or if the name change seems religious, political, etc., then you come off like a misguided extremist, who is trying to politicize the workplace or "make it all about you" and thinking that is more important than working together. They worry that they'll have to dance around you" or "watch their mouth around you" - and that hurts your relationship badly. For instance I would never call it a "deadname" in the workplace because that implies a gravitas that would make them worry.
What happens, when you don't kick up a fuss, is others will do the kicking for you - people will kick themselves when they use the wrong name, or their colleagues will give them a nudge. You want to be seen as the gracious and patient one, so they will invest themselves in using the right name.
90% of what I did was put the new name in my email sig.