A video would be nice, but I see an easier, cheaper way to get this song some massive exposure on the mainstream... how about the next time Robert Zubrin (aerospace engineer who's written extensively on terraforming Mars), or Richard Hoagland (former NASA consultant who revealed the presence of liquid water on Mars over 10 years ago and speaks openly of its suitability for habitation) are guests on "Coast to Coast AM" (5 to 8 million listeners nightly), use "Moving to Mars" as bumper music coming out of breaks?
Hoagland is especially hip to pop culture and he would pick up on the lyrics and point how how poignant they are to the subject. It would be a great way to get this song in the minds of many who would otherwise not have a clue about it
I'm going to write the producer of C2C AM (Lisa Lyon) and suggest this to her. Both of these chaps are fairly regular guests. Zubrin's almost always talking about Mars, and Hoagland speaks about it in roughly half of his appearances.