I just found out earlier today that redbus wasn’t showing up on certain devices, specifically "small screen" phones. Since I had originally targetted android SDK 1.5, and support for small screen devices appeared after that, by default they wouldn’t show up in the market for them!
The docs on the specifics are here.
Basically what I did was switch the android project to using SDK 1.6, but set the minSdkVersion to 3 (so it’ll still appear for SDK 1.5 devices). Then I added the new line:
<supports-screens android:smallScreens="true" />
So make it appear. According to the docs, with SDK 1.6 this should default to ON so theoretically I don’t need it. However, since I don’t have any small screen devices to test market browsing on, I decided to play it safe and make sure it is enabled.