As others have said, you have the skills to create this type of game already. The basic idea behind it is to use an image file that has 32x32 (or whatever size you want to use) "tiles" in it. You draw each tile basically the same way you did your animation for sonic (if you had one image that contained all the animations). The way you would add depth to the game would be using something called Z-order which is just means you draw the ground layer before the collidable layer so things like fences appear above the ground layer. if you want to have a tree cover a player, simply draw the top part of the tree on the sky layer as opposed to the collision layer (where the bark of the tree would be)
I've been trying to make a game like this for years but I keep getting caught up on design issues and whatnot. I want to make it as perfect as I can which is why I haven't even gotten into the development of the actual game yet.....
Anyway, take a look at Tiled for an easy/opensource way of creating your 2d maps. Then you can roll your own reader for the xml file that tiled produces, or you can use http://code.google.com/p/tmx-parser/
Let me know if you have any other questions about this style of game. (Been trapped here forever haha)