I agree that a recommendation system would be awesome but is it really that hard to find a new subreddit? The search feature at http://www.reddit.com/reddits/ seems fine.
The r/gaming example is a perfect example of why a search system doesn't solve the problem. I'm already subscribed to r/gaming so I don't think I need to search for another gaming subreddit. Another example would be r/battlestations, a subreddit for people to post their desks, I would never think to search for "battlestations" but it's a subreddit that I like a subscribe to (which I only found because someone recommended it elsewhere on reddit).
Search only helps you find what you're looking for, it doesn't help you find things you might be interested in.
The reason you wouldn't think to search for "battlestations" is presumably because you don't visit 4chan. That entire subreddit is actually an example of a part of 4chan leaking onto Reddit.
