Muppet Time Travel (also known as Muppet Time Machine) was mentioned in a Jim Henson Company press release in 2001. A script was written by John Derevlany. The concept involved Animal stumbling into one of Dr. Bunsen Honeydew's time-traveling appliances, and going back to the Stone Age, where he inadvertently becomes evolution's missing link.
Finding themselves living in a world of humans descended from Animal, including the wild Postman Joe, Kermit and friends must go back in time to fix things.
Postman Joe is a character who would have appeared in the optioned but unmade film Muppet Time Travel. He is described in the script as "an extremely normal, All-American-looking, human mailman." The character would have likely been a vehicle for a celebrity appearance.
Besides delivering a number of legal documents to Kermit early in the story, Postman Joe is used to illustrate the paradigm shift that takes place once Animal alters history. After Animal's departure, Postman Joe is the first human to be seen with Animal's features, voice and mannerisms (including his trademark attraction to females and drumming abilities).
Postman Joe would also have played drums on a song mentioned in the script with the proposed title "The World's Gone Animal", performed by the Electric Mayhem.