Come on! Do it!
I'm currently playing this game together with my roommate (we both bought it separately after it was priced off on steam), and love it, but it sucks that we can't play it together somehow.
So I've been reading a couple of suggestion posts on multiplayer, and a lot of "fans" seem to defend super meat boy that it would be worse off with multiplayer. I don't necessarily see why, especially not if it's built on top of the current game.
My favorite idea would be to have some kind of ghost of your opponents best time replay each time you die.
It wouldn't even be that hard to implement. Just send your fastest replay to each client when you achieved a new record while playing the game. Every time your opponent dies, you start again together with that fastest replay of him.
So no waiting, easy to implement, and fun because you're constantly trying to best eachother. It's not even real multiplayer, cause you only send replays to eachother. You don't even have to stream anything. Your local client plays the fastest replay as soon as you restart the level.
By the way, this should also work for single player. See the ghost of your best time while playing.
Also, why not give the possibility to see ghosts of people (while playing a level) with similar scores of you in the rankings? I'm sure it would reveal a lot of cheaters. (I've noticed a lot of people finished levels in 0.0 seconds, which seems odd).