Here's the theory about what's supposed to be patentable:
Statutory material: No matter how brilliant, a poem, law of nature, mathematical algorithm or computer program is supposedly not patentable. Lots of details at http://www.uspto.gov/web/offices/pac/mpep/s2106.html
Novelty: It has to be new. This is where prior art comes in.
Non-obviousness: This is the test for patenability you're talking about. It can be hard to judge obviousness in hindsight. There are so many specialty areas today that it's unreasonable to expect the patent office to be able to determine what would be obvious to an ordinary practitioner in every area of invention.