You need a good sense of speed. I got so bored of rolando because the rolandos just move so slow. Make sure there is a good weight to the character with momentum like in the original super mario which in my opinion is still the greatest platforming experience ever. Varied level design with not a lot of filler crap I want a challenge I don't want to walk through empty level. Catchy music that fits with the tone, I like soosiz platforming, but the music is just so out of place and annoying. The game is like a cool platformer but the music is like 1920's short film music. It's weird.
I think there are two levels of things to think about. The must haves - Speed - Worlds (platformers, etc) - good music - Good graphics - Strong and solid controls - Bosses Things that make a game stand out - Powerups ( I did not like castle of magic, but I loooved the powerups) - Secret stuff (hidden worlds and challenges - Special Stuff (in Soosiz it's the gravity thing for example, in Rolando it's the controls, etc) I would also look at Bounce on which is a good platform. As for people thinking games are too kiddie, I like the cute graphics and I love the cute like chicken in Tori Toki
Good thread We're working on a platform game right now. It will be a 2.5d style game in the tradition of Little Big Planet. Lots of work to do on it though to get it to that stage...