Honestly, you guys want to make this look like it's for everyone, but many people out there don't use their brains. A huge chunk of people use Windows, IE, and QWERTY, and that group of people, who don't think outside the box, are the people who may just be hardest to target.
I think that it's important to help them think outside of the box first, which unites your objective with that of the Linux community in general. As this is the case, I think it's important to get colemak included with major Linux distributions' layout lists.
My recommended course of action: officially put colemak under the BSD license. This takes it from "public domain" to "open source", immediately making it more attractive for inclusion in major Linux distros like Ubuntu. Contact the Linux keyboard layout software people, let them know that you exist, and why you're worth including in with other pre-installed keyboard layouts.
Make your motto: "Colemak: Rediscover Typing", to make you seem more familiar to firefox users. Or, you could have multiple mottoes of varying lengths to cater to different uses, and help make the process of elimination easier by having more survivors ;) . Say, one for a simple catchphrase, one for t-shirts, one for people with RSI, etc.
Colemak: It's what the doctor ordered.
Or, hey, you could play on the alt-alt theme, and rhyme, and throw in clichés, and yet another catchphrase, all at the same time. (man I love special characters on the fly.)
You don't use Windows and you don't use a Mac.
We don't use QWERTY and we don't use Dvorak.
Third time's a charm. Colemak: designed for your fingers.
Ok, now I'm probably just going overboard.
All said, my main point is that you're not going to get very far by targeting the brain dead masses (sorry to be harsh- maybe I'm slightly elitist...), something us other life hackers have learned over the last 5 years fairly well. Target the rest of us nerds. Target family members of the dvorak people with inferiority complexes ;) , target Linux and BSD users, Firefox users, slashdot-digg-engadget readers, etc. And remember that the use of an official BSD license will make you more attractive to them.
I know you want to be out there for everyone, but you already have windows and mac covered. And the BEST forms of advertisement, in fact the only forms of advertisement I cooperate with, endorse, or respect, are facts and satisfied customers. The facts you have well covered, and the quickest way to get the most satisfied customers is to target us open source nerds. I have proof that this works, too. The only person I've convinced to switch to date is a member of this group, and if I wasn't one, I would never have come across this site. Once all of us use it, it will simply be a matter of the general public coming to their senses.
Side note (as if this post wasn't long enough): it would be very nice if the Linux installation wasn't so hard. I'm fine with command prompt stuff, but when it doesn't work right the first time, it's easy to give up on. Perhaps someone here could make an automated Linux installer or .deb archive?