How about

Arf A Mo Reely Band

Ava Narna Jiggy Band

Geri Attric Barney Band

Cay Lee Barn Band

I always think a cachy name helps people to remember the band name. One other thing is to possibly use a name beginning with A as you will probably be one of the first bands they find in the list.

I do remember once trying to help put a Ceilidh on, and nobody in the area new what a Ceilidh was. However, when I said it was like a barn dance but better, that seemed to work. I also told a Scotsman and he knew immediately knew what a Ceilidh was as it seemed thats what they called it up there.