Even just as a user, I've noticed this. Discovering good, reputable apps has become more difficult. The best way I've discovered to see a collection of functionally similar apps is to find one app that does close to what I want, then select the "related" link. It gives a much more useful list of apps than searching based on keywords.
Good trick. They are different algorithms, and it looks like the guys working on the search of relevant, similar apps are doing a better job! (I know one of them personally, so I may be biased.)
It's paradoxical that this comes from the #1 search engine.
Not the first time something like this has happened. Their Groups search was broken a few years ago as well, and it took some effort to get them to finally fix it:
http://www.wired.com/epicenter/2009/10/usenet/
We launched a new application just when this issue started: our application didn't appear in any search. Then it finally got indexed, and our download rate doubled. From 1st of July, it halved again.
We didn't even start to monetize it, but it has certainly taken much of the fun off of developing it. This must have been a very big hit on some other developers.
