Further confirmation that search is completely broken in the App Store. Read about this app on my work computer, fire up the App Store on my phone, search 'Letterpress', Apple's Cards app, and a Letterpress Handbook about actual letterpresses.
It usually takes a while before new apps can be found with the full text search.
Do we know how long ago it was launched? Sometimes it doesn't populate in the app store at all for the first few hours, even though it can be accessed and downloaded from direct links.
If he just launched it'll need to be indexed first.
Same here. Can't find the game at all on my iPhone.
Had the same problem. I just went to www.atebits.com from my device and clicked on the itunes link from the site.
This isn't a case of search being broken, but rather of Apple being very bad at distributed systems, and it taking a ridiculous amount of time for new apps to fully propagate.