I love this idea! I'd personally change all my characters to boys if that meant I could start with a new name on this game and leave the awful people who've harassed me behind!
However, a reason they may not have implemented this is because there are very few names that are the same on a girl than a boy. For example, Fiona wishes to become Alric. This would involve changing the characters gender as well as their name. Therefore, as good as an idea as this is, it may be hard and a lot of work for KI to implement. You also run into the problem with leaderboards and your friends not knowing who you were previously.
Despite the cons above, I wholeheatedly believe this is DEFINITELY worth looking into!
If they can figure out how to to allow us to change our names, I'm sure that this will eventually follow. As it is now, I would use the level 50 potion if you are high enough on another wizard and at least start in Celestia instead of Wizard City and just create the new wizard.