See, I kinda agree with the idea that the Muppets have always done classic stories... think of "Hey, Cinderella! and "The Frog Prince", and then there are the Robin Hood and Alice in Wonderland episodes of TMS, the Rowlf as Merlin segments on The Jim Henson Hour, the old Muppet Press Robin Hood book, and of course, MCC and MTI (which are both good movies, a point that is often forgotten on this forum). You could even stretch it a bit and say that GMC and MTM are genre movies retreading familiar ground with age-old plots.
My point is that the Muppets have always retold classic stories their own tongue-in-cheek way, and they've always done them well.