Prior to that, it was going to be MuppetsinSpace; aliens would've abducted Kermit because he resembled their leader, forcing the other Muppets to journey into space to rescue him. Though it was announced first, it got passed up in favor of the movie we got; Welch's Jelly jumped the gun and released collectible jars based on the ultimately-unmade movie.
The film was originally going to be an actual musical, with the song "I'm Going To Go Back There Someday" from The Muppet Movie making its return, this time, in reference to Gonzo's ambition to find his family. Then someone said, "Naaaaah! 70's funk!"note It is on the soundtrack album, though.
The rock band Ween wrote an Image Song for Gonzo, entitled "Eye 2 The Sky". According to IMDB, they sent it to the people making the movie around the time the "70's funk" decision was made, and were then asked to do a cover of "Brick House", to which they declined. (The original Commodores recording plays at the beginning of the movie.)