Marketing is something that you probably should have been thinking about well before you released the game. That said, at least you're thinking about it now. A lot of app developers think that "if you build it, they will come" and with all the noise in the App Store, that's just not going to happen.
Presumably your game has a specific target audience in mind, so the goal of your marketing efforts should be to reach out to that audience. Figure out where your audience lives online.
As a last resort, you could drop a link onto HN and hope people follow it. ;)
peteysd is sort of right - a target audience has to be established before the app is developed. Otherwise you're creating an app "for everyone", and the truth is that selling apps "for everyone" is much much harder than for specific target. Targeting is king.
In your case I suggest to target people who like brain-teasers and also tetris communities - there must be some of those. You need to find them and talk to them. Another angle is teachers and people working with children - you can try to pass it as "helping develop brain, reaction, quick-thinking" or whatnot. A long shot, but it doesn't look like you have too many options.
A few practical advices:
You can't improve what you don't measure. First step - stop sending out iTunes links and start sending out shorted and click-counted linkshare iTunes links - not only you will know how many people clicked, you will also know how many of them buy.
Your demo video is doing a god job but is too long. Make it 30-60 seconds to improve chances of people even starting to watch it.
Everything I heard about AdMob is that it's making money for them and losing money for developers - there are clicks but there are no purchases. You could try, but I wouldn't expect much from it.
What were the encoding parameters? Resolution, bit-rate etc. I tried to put couple of demos on YouTube and they don't look nearly as good, even though the source video is very crisp.
Presumably your game has a specific target audience in mind, so the goal of your marketing efforts should be to reach out to that audience. Figure out where your audience lives online.
As a last resort, you could drop a link onto HN and hope people follow it. ;)