A couple of things. As an official old person on the boards (and you youngsters should be in BED ALREADY!), I actually watched TMS in "real time," watching the show unfold. I was a card-carrying member of The Muppet Show club, and I saw the movies and the show episodes as they aired. (Yes--you may envy me now....)
Lena Horne was the first "OMG" talent the muppets got on TMS, but keep in mind that many, many famous stars had already worked with Jim on SS and other things. One of the problems they encountered with guest talent was that the show was not filmed in California or New York. This is because American television stations were TOO STUPID to give Jim a shot on the regular, three-network tv of the time. So, guest stars had to not only be willing to FLY TO ENGLAND, where the show was filmed (May God Bless Lord Grade), but they had to be willing to do so for a show that was only 30 minutes. If they had filmed in Hollywood, they would have had more people interested and available, I'm sure, but I also go the impression that Jim picked people that he liked, that he thought would be interesting PEOPLE, not just interesting guest stars. By the time the first season was over, EVERYONE who was ANYONE was clamoring to get on a plane and fly to England to do ANYTHING JIM WANTED.
Hope that helps fill in a little.