I'd never change my name, but I've been in a lot of situations where I wished I could. This would be nice to have for many players, but ultimately it might cause problems.
My only problem with Spyike's rules is this:
Someone can remove their previous name from their signature and commit a scam/multiple scams before a mod notices and TWC's/Temps them immediately for removing it from their sig. However, since the first two requirements would make it so that you're virtually 100% trusted to begin with, changing your username probably won't help any scam. Eh, my $.02 at least.
As for the "Only Minor Changes" that Skele/others said:
Why even waste the energy to get this set up if people can only change their name a bit? This excludes most people from even getting this option. Rsaccounttrader, for example, couldn't really change it at all. What's "similar" to Rsaccounttrader? (I'm referencing him because he has already posted that he would request a name change, and he also would almost definitely fit any sort of "trust test" required for this.) Why is it fair that only some "trusted" members can get this option but not others? Sure, it'd be nice if someone wanted to capitalize their name or something, but that option exists with a customized username anyway.