If petrification is just going to reverse when the medusa is dead, then why not just call it 'stunned'? In fact a stun could be nastier than that.
I think the 4e designers were attempting to both have their cake AND eat it too. They wanted a monster that would be fearsome, so they gave it a watered down version of an instantaneous kill effect, but at the same time they didn't think it was 'fun', so they watered it down. What they ended up with is what you end up with in most such compromises, the worst of both worlds.
It is still a total kill effect even if it takes 3 rounds to kill you and only works 25% of the time. OTOH it is clearly a lot less awe inspiring than the old time "if you are hit you die" mechanic.
Personally I think the problem is that the 4e designers have lost sight of what the fun in D&D is to a certain extent. They have become so focused on one particular vision of the way to have fun that they've railroaded the game down a specific path that only caters to that one idea of what having fun is. To ME and the players I DM for having fun means really being challenged. Having truly frighteningly powerful monsters and dangers that might well be able to snuff you out in an instant. I'm not saying that is all that is fun in the game or that such monsters should be the norm, but stripping that element out of the game IMHO isn't ADDING to the fun of the game, it is just removing a possible dimension of fun simply because it didn't happen to float their boats.
So, be welcome to come play in my world. You get hit by the gaze of the medusa, then baby you're petrified. But you can be very sure if there's a medusa around, everyone knows it! Very few and far between are the parties that dare take on that adventure, and they prepare well, or they join the statue collection. If the players don't like that kind of fun, then I'm not going to ram it down their throats. I guarantee you that even if the player who's character got petrified gets a bit bored waiting for the fight to end so they can introduce a new character, they will remember that fight! In the long run the game will be more fun for all of them, and when they beat those odds they'll remember it a lot more than they remember the 847th Orc they killed.
So I have a message for Mr. Mearls and crew. Don't overdo it. You may be playing game designer, but try to be cognizant of the fact that you're way is not the only way, and remember that if you try to homogenize us all into playing only one way, some of us will just play other game systems and you'll lose customers. I like 4e fine and that isn't a criticizm, just an observation.