Almost forgot about the
Cracked guide to prog, and their section on how to name your prog band:
You really have two options when choosing a prog band name. You can either go with something "simple but random", like Yes, Rush and Camel (may we suggest "Spinach", "Taco" or "Hat"?); or you can use a complex title if it is sufficiently outlandish.
The second route is riskier, but the payoff is enormous if you nail it. Enthusiasts love to quote their favourite obscure bands, and the zanier the better. ("Oh, you haven't heard of Mr Bungle? Next you're going to tell me you aren't a fan of Van Der Graaf Generator.")
Some suggestions to get you started:
Interstellar Spinach
The Epic Taco Project
Hat Dimension
Vintage examples are The Mars Volta and Porcupine Tree. In fact, The Vintage Examples would probably work, too.