I’ve read Dave Barry books ever since I was a little kid and I always noticed that every time a strange phrase would come up, he’d write: “note: wouldn’t ‘turkey rectums [or whatever]’ be a great band name?”
Now I see it all the time on the Internet, especially right here on this forum. So did Dave Barry invent this, or has it always been around?
I never saw it before Dave Barry, I would say he at least popularized it.
I do find myself thinking it every once in a while. You say or write something …
Click: That would be a great name for a band!!! 
Oh, and by the way…
“Turkey Rectums” would most assuredly not be a very good name for a band.
It would, however, be an accurate description of a great many existing bands.
Touchez.
Personally, I think
**
A Great Many Existing Bands**
would be a good band name.
As a bit of a hijack, I actually said “You know, that would be a good band name” today to my boss, his boss, and a co-worker. 
They agreed with the sentiment, and laughed a bit.
(The phrase in question?? I can’t remember exactly at the moment, but I think either ‘Nebulous fuel inventory’ or ‘Nebulous fuel surplus.’ )
Steve Allen on the old (read original) Tonight Show came up with some very similar way of naming bands and came up with some very similar names to Turkey Rectums, I might add. He did it by having a barrel full of adjectives and one of nouns. He would dip into each barrel and take one out.
To this day I remember my favorite, Polish Sweatsocks.
I’m sure this has been around since at least the 60s psycedelia genre began. A friend and I have been doing this continually since at least the 80s. I’ve always had friends who do this. It’s just a ubiquitous concept, whether among comedians or music geeks.
One of my lines used to be that I didn’t understand how bands or racehorses got their names. Now, because of Dave Barry, I understand how bands get their names. I’m still wondering about racehorses. And Japanese Anime (Bubble Gum Crisis!!!)
One of my friends and I used to say ‘That would be a great band name’ in the early-1980s. (Remember, this was when Punk was still going strong and the bands had some interesting names.) I never heard ‘Band name!’ used by anyone else until I came to SDMB.
Since we came up with the phrase independently, I would say it’s ‘always been around’ and that Dave Barry just popularised it. (Or else, he also came up with it independently.)