Those would be the Spongmonkeys of internet noteriety. They originally made an appearance in this flash animation.

http://www.rathergood.com/moon_song/

I don't know how Quiznos got Rathergood to do an ad for them, but I remember dropping my dinner fork when I first saw that commercial while saying, "What the deuce? They've escaped from the Internet!"