But how does the app handle older apps? What if I bought an iPhone today, could I use the app to find older applications? And if he adds a way to browse the app store via the criteria you want, won't Apple shut him down for duplicating functionality that's built into the phone?
It handles older apps through its search interface. Search and "New" are two distinct tabs in the app. You can also block specific apps and developers from showing up in your search results.
There is no rule for the app store that you can't release an app duplicating the functionality of another app, even Apple's own built in ones. That excuse that you've seen handed down with some rejections is just BS, since Apple reserves the right to reject any application for any reason.
He's had multiple revisions all approved.