From Muppet Wiki

The Genie of the Toothpaste appears to Cookie Monster and offers him three wishes in the story of "The Monster's Three Wishes." In this sketch, he was played by Jim Henson. (EKA: Episode 0764)

A similar Genie also appears in a Season 8 Sesame Street News Flash sketch with Aladdin, where he was played by Jerry Nelson.