There've been lots of variations on flight, and different ways for Mario to fire off projectiles or become invulnerable. I think new Mario power-ups should focus on new things for Mario to do. Galaxy 2 was great for this with Cloud Mario (which has become one of my all-time favorites, right up there with Raccoon Mario), Drill Mario and Rock Mario, and even new power-ups for Yoshi too.
I'd like to see Sticky Mario. Mario covers himself in goo and can stick to any surface. Sort of like the Spider-Ball from the Metroid games. Maybe he could throw globs of slime to attack... or shoot webbing and make the power-up Spider-Mario? If you wanted to make it completely broken he could also lay down web-platforms like Squitter in DKC2-3 or like Cloud Mario's clouds.