The only times I can think of where a re-branding exercise has worked well, have been where the brand started off in the mud and they fixed their image rather than the name.
Specifically, Skoda — and when they did the transition, their adverts were very much aware of the need for an image change: https://www.youtube.com/watch?v=ZWTJ_TPraLQ