I'm with Marc... cross platform is the way to go - but not only that, you need to spread the word as much as you can.
My "Escape from Alcatraz" game is doing better than I expected: around 15k downloads, most of them (around 9k) from iOS.
I submitted the game to several review sites (I just googled "Android review" and "iOS review" - but I don't think any review has been published about it), I posted on twitter, on facebook... and although I do not have many followers, the word is spreading I guess
Some evidence that my game is 'appearing' to the public is that its listed on Metacritic and on GameSpot (first of my games to achieve this!), and I even found a page where people asks for hints to pass certain parts of the game =)