Old characters not given rename

Hello! Recently I have been playing on Icecrown again after a 6 year hiatus. In this time my characters have been putt in cold storage and their names released and assigned randomized names.
Since logging back in, I've only been able to rename 1 of 3 of my old characters.

Any ideas?

I think deleting Cache -folder might help. You can try repeatedly logging them to see if it helps.