A recolor is a character loosely based on another official character; for a recolor to be officially defined that, however, it must also lack creativity. If you look at the Mario series, there's the Hammer Bros. and Fire Bros., Lava Piranha from Paper Mario and the Piranha Plant boss from Yoshi's Island; Kirby and the unmasked Metaknight (and don't forget Dark Kirby from the mirror world) have a similar look too, and just about the same goes with Megaman and Protoman.
The main reason those characters mentioned aren't considered recolors is because they still contain creativity. Fire Bros. is a subspecies of the Hammer Bros., as is a ton of other kinds of creatures, from Sumo Bros. to 1337 Bros. from M&L2. It's believable, and not overdone either. While Kirby and Metaknight unmasked look very similar, minus contrasting colors, their personality, traits, and role are extremely different. Megaman and Protoman are also not considered recolors, due to the simple fact that it isn't overdone. They look similar, but there's no real reason to bash them anyway.
It's a different case with the Sonic series. Amy isn't exactly a recolor of Sonic; she not only looks very different (old or new design, whichever you prefer), but she's also the second hedgehog to appear in the series. There's nothing wrong with having another hedgehog around, right? It's not like they're a one-of-a-kind species or anything. Something has to be said about Shadow and Silver, though. Practically the only differences between Shadow and Sonic is that Sonic is blue and Shadow has red stripes. Other than that, they're the same in design. The real difference in SA2 was that Shadow took role of a villain; he was also a dynamic character with backstory that ended up persuading him to help Sonic save the world for the cost of his own life. That's enough to make him a legit character, except Sonic Team screwed the hell up by bringing him back to life, eliminating the point in the heartfelt atmosphere of the SA2 ending. Worse, they dulled his personality to "OH WHY MARIA WHY I MUST MAKE SURE NO ONE SUFFERS MY FATE", ruining credibility, and giving him the reputation of a needless recolor. Silver isn't any better either. Silver's design differs a good deal from Sonic's compared to Shadow -- in fact, he looks more like a peacock than a hedgehog. That doesn't save him any, though; he's the fourth hedgehog to appear in the series, and doesn't seem to have much personality. His backstory? "im from the future i need 2 find the iblis tiger"
Most fanmade characters can be considered recolors, if they're based on major characters of a certain game. Super Mystic Sonic, Nitro, and even Senku are recolors, because the idea of another hedgehog has already been done a thousand times. If Sonic has a thousand other official characters as friends that look a lot like him, then his design can no longer be considered unique.
Lee-way can be made to some minor characters, especially minor enemies. Some great examples can Emerald Sir Kibble (fan-made), Kooper (official), and Master Head (SSB fan-made). The plain reasoning is because they're never done. Do you ever see someone naming themselves as Emerald Kibble? I sure don't. Fan characters are fan characters no matter what, but with enough rarity of the concept, it can be considered legit enough to be above the rank of a recolor.
I can barely name any Sonic fan-characters that aren't just recolors. Hyper Metal Sonic X is the coolest fan character I've seen yet, recolor or not. For those of you looking to make a fan character based on Sonic the Hedgehog, why not base your character on some of the minor enemies? You know, like Grounder or Crabmeat. It'll look a lot more respectable just because of its rarity.
