The live nerd music duo Paul and Storm are a frequent opening act for Jonathan Coulton on his tours. Despite being just an opening band, they have gathered a rather large following due to their unique on stage mix of comedy and music (or as they put it: "Music. Occasional nuns and pirates.") It is in the comedy part of their show that this meme took root and truly soared to popularity after their concert at PAX 2010.

Though Paul and Storm have mentioned they did not start this line of jokes, and they can't remember who did, they are known to have popularized it with many smart jokes of this form.

There is a Twitter devoted entirely to retweeting these sorts of jokes. (http://twitter.com/XIsMyYCoverband)

Paul and Storm themselves use different forms of the joke, Paul usually using the more standard "X is my the name of my Y cover band" whereas Storm will use the form "X is the my Y tribute band" But both are the from same joke

(partial) LIST OF JOKES (all changed to the standard form)
"Oblong Circle" is the name of my Oingo Boingo cover band.
"Start Being Quiet" is the name of my Belle and Sebastian cover band.
"No Pirate Left Behind" is the name of my Jimmy Buffett cover band that only does 'School House Rock' songs.
"Drunken Wheaton" is our Wheezer cover band.
"Wheezer Buddy Holly Silence" is our Elvis Costello tribute.
"Dane Cook Holding An iPad" is our Nerf Herder tribute band.
"Hardcore Method" is my Slipknot cover band.
"No Rimshots For Paul" is my Wings cover band.
"The Underrumbles" is my Barry White tribute band.
"Monty Hall Treasure Dungeon" is our Rush tribute band.
"Bad Motivators" is the name of my George Thorogood cover band.
"We Don't Actually Have to Fucking Do It" is my Milli Vanilli cover band.
"I Broke A Couple of Nerds" is the name of my They Might Be Giants cover band.
"I Broke A Couple of Nerds" is also also my Rocket From The Crypt cover band.
"Surly Nerds" is the name of my w00tstock documentary on the IFC.
"Laugh Away From The Mic" is the name of my Tay Zonday cover band.
"More Bands Geeks Than Usual" is my Polyphonic Spree cover band.
"Sweaty Hot And Stinky" is the name of my Kingston Trio cover band.
"That's Not Funny But I Like It" is the name of my Paul and Storm cover band.
"Nice Precision Gamers" is the name of my Anamanaguci cover band.
"Shut up Wesley" is the name of my Lenard Nemoy cover band.
"Troll Bait" is the name of my Foghat cover band.
"Never Gonna Give You PANTS" is the name of my Tool Cover Band.
"Grinnz Charts Tool but Quotes JoCo" is the name of my Lady Gaga Cover Band.
"Tofu Rush" is the name of my Pretenders cover band.
"2500 sauve pirates" is the name of my Great Big Sea cover band.
"More Cover Bands" is the name of my 'Blue Öyster Cult' cover band.
"Waiting for Coulton" is the name of my 'Paul and Storm' cover band.
"Unciprocated Dingle-Arm" is the name of my Tool cover band.
“Fickle Finger of Fate" is the name of my Cinderella cover band.
"Urogenital Frenulum" is the name of my Hard and Phirm cover band
"Vaginal-Rectum Area" is the name of my Megadeth cover band.
"Trumpets and Beards" is the name of my Blood, Sweat and Tears cover band.
"Fuck you, Time!" is the name of my Morris Day cover band.
"I Like the Way Your Voice sounds" (in reference to a teenage voice crack) is the name of my Brady Bunch cover band.
"Oh my Nose" is the name of my Brady Bunch cover band.
"Deploy the Yoda" is my NerfHerder cover band.
"Jaunty Little Stagger" is the name of my Popes cover band.
"AR with and umlaut" is my Scorpians cover band.
"Those meddling kids" is the name of my new kids on the block cover band.
"That's more like it sheep" is the name of my Justin Beiber cover band.
"We gotta move this shit allong" is the name of my Justing Beiber cover band in 2 years.
"Never underestimate the attention span of a tween" is the name of my Minuto Cover band.

Videos with cover band jokes in them:
PAX 2010:

HELLISHLY long video:

Eternal Arr from Dan Coulter on Vimeo.