My app is available in iTunes but not from my iPod's search

I made a physics arcade game (with a metaphorical twist!) called Enlightenment Vision, and I see it available on iTunes, but when I do a search for "Enlightenment" on my iPod my app isn't shown. I didn't get an e-mail from Apple announcing its launch though, which is strange. (I got one a few days a开发者_开发技巧go for a naming inconsistency in the binary). I sent Apple an e-mail but I'm wondering if anyone else has had this issue? Promo code available for the best answer :)

How recently was it added to the store? It could be they have a caching system of some sort for their huge user base and it could just not show up on the optimized mobile version yet.

If I search for "Enlightenment Vision" in the App Store application of my iPhone then it appears, however the app name does not appear as an auto-complete suggestion as I start typing. Are you actually pressing the blue Search button after typing it in?

Edit: If I search for just "Enlightenment" then it appears as result #4 in the results, but again not at all as an auto-complete suggestion.