The average user of T-Mobile USA’s Android-based G1 phone has downloaded more than 40 applications from Google’s application store Android Market, but T-Mob CTO Cole Brodman thinks users would access a lot more of them if they could just find more that appealed to them, according to PCWorld, reporting from Dow Jones (NYSE: NWS) Wireless Innovations conference in Redwood City, California on Tuesday.

This is hardly a surprising remark, but it highlights the growing problem of search on mobile devices. When Apple’s App Store first launched, it was assumed that the store had leveled the playing field for all mobile apps and that the “cream would rise to the top.” But as the App Store gets increasingly crowded—the latest stat says there are now 25,000 apps on offer—this is obviously not necessarily true, with many developers complaining there must be a better way of getting in front of consumers.

Brodman, meanwhile, already finds Android Market’s 2,300 applications too many to wade through. He said the store really needed good search and customization tools to help consumers sort pinpoint what they wanted, rather than just relying on what they have now—rankings based on user ratings, popularity, and when the app was released. Brodman wanted to see features that could automatically present consumers with apps that matched their interests. 

The other thing that Brodman wanted was for application stores to be made available to those using feature phones, rather than smartphones, as these phones still make up “the vast majority” of handsets sold.