Naming my characters is one of the hardest part, but one that I can go back to later. I usually have a concept, a back story, and a costume in mind, and hopefully a name that hasn't been taken. For me, the playability of a toon is the combination of its power set, costume design and name. If one of those things is off, I just delete and start over. I usually start off with some pretentious emo name like Destroyer of Worlds type or the typical color + talent or noun. But later I change them to names that make me smile and say "yup, today's a good day to be a hero" =).
Funny enough, I have a character with a power set and costume that I really liked. But I just couldn't think of a worthy name. So I named it Six-Six (because it was the 66th alt I was working on). Somehow, the name grew on me and he's my favourite toon to date.