Long story short: the game mechanics itself aren't (and can't be) protected in any way - everything else (the media/names) is.
As for the media, if you create a "new work of art" then it's yours to own (as soon as you create a new work, even if it was "inspired" by a previous work, it's no longer a copy, and immediately all the copyright laws become irrelevant). The issue that Onyx refers to is that if you create a new work, although you *do* own it, you may instead be affected by the trademarks laws, that say you can't promote something if you might confuse people into thinking that it is someone else's product.
Hence legal battles preventing cola companies from using red packaging, because consumers looking for Coke just grab "the big red bottle".
The issue with e.g. Sonic is that if your new Sonic looks very Sonic-y, then the owners may feel that you're confusing customers into thinking it's "Sonic 2" (or "sonic 10" or whatever
).
There are exceptions, like if there's some obvious reason why it's not a sequel. E.g. a pastiche, where you are clearly taking the mickey, is nearly always allowed.
You should, for instance, be able to have a red hedgehog. So long as he doesn't have Sonic's graphic style (I'm assuming they've trademarked that). They might - conceivably - have trademarked "hedgehog in computer game"; if they had I doubt it has any relevance in the world beyond making some weiner lawyer feel impressed with himself - if you could protect *anything* you can bet MS would have trademarked "Intel-based Operating System software" by now
. NB: there are lots of "trademark laws", not just the ones dealing directly with trademarks (which are a specific type). You can get something covered by some of them, even if not by the "TM" ones. E.g. in UK law you can get the "shape" or "design" of a physical item protected without being distinctive enough to have a TM on it.
Beyond that there are lots of little laws and finicky details that you probably can't be bothered with. And I'm not a lawyer to advise you on specifics.
