Like The Count said, I am a dedicated Muppet fan. For some films I know the year. (Some of them were found in the SS albums in the copyrights. "The Ballad of Casey McPhee" I found out was made in 1975, so I associated the cows with that year.) Plus I have several films on tape that feature those Muppets (including "McPhee" and "News Flash") and pictures I found at websites (such as Hooperfan, where I saw the 1979 pic). The earliest I've seen the refined Natalie was in the "Wet Paint" song (with How Now Brown) in 1984 (I found the date in the "SS Best" album, but some of the dates on that album were different than other ones I've seen in other albums. Also, in the song, she was joined by Maxine, who I just remembered was also named MacMuffin(last year) and Bissie-Bossie(this year)). I knew about Cathlene because I had her name written down on a piece of paper, and I remember her on "A Muppet Family Christmas".
And to punkNpuppets:
The original Gladys can be found on the video "Big Bird's Story Time" in the "Humpty Dumpty" News Flash sketch. Anyway, both of the cows were a bit thinner than the ones today. Their eyes, horns, and hair are the same, but their heads were a bit slimmer, and their (a bit smaller) mouths looked as if it was carved in like the rest of the body( I remember that in the "Hey Diddle Diddle" sketch that when Natalie looked into the camera, you can see a hole in her mouth when she talked!).