Providing you're not actually copying either the code or graphics then you're clear on copyright law, so it's then down to patents/trademarks. Well-known characters will probably be trademarked (Mario, Sonic, etc), as will the game name itself, and aspects of gameplay (or the techniques behind them) may be patented.

The overall look-n-feel of a game (particularly a simple one) can also be protected ("trade dress"). See this Tetris lawsuit for an example.