I know you've said it doesn't make for a good looking trailer, but have you considered selling the gameplay more straight?
Maybe it won't make for an exciting trailer, but at least the audience will know what the game is and that might be a more important first thing to do than anything else. Looking ugly and having to be long winded and verbose to explain how the game plays might be better if it means getting far enough away from everything else that the game actually stands out.
To be honest I think if Shattered Haven was presented as a "adventure maze-puzzle game on steroids" in advertising and if the story was left for when people actually played the game then more people would have understood it better, as that would have shook off the "cheap zombie game" image early.
Not to mention, if you're going to sell the theme and setting then that pool has already been pissed in so to speak. Just search through Greenlight for a while.
Maybe you shouldn't try to be too concise at first and just get the point out so your audience knows what the game is even if you have to talk more, then after that start selling the theme and setting.
I kind of feel like Shattered Haven and didn't do enough of the former and because of that didn't do well with the latter because the audience was still scratching their heads.