FYI, I have the same (or at least similar) problem. My phone (Sony Ericsson x10 mini) cannot find the app. Even if I go to Appbrain or any other website, it generally redirects me to Android Marketplace which then shows up as not found. I thought it was because my phone is running Android 1.6, but my wife's phone is also running Android 1.6 (different phone though), and her phone finds it ok. Very frustrating...