I've been wondering if the "obviousness" angle hasn't been emphasized enough, especially to the non-programming world. To rephrase above and earlier comments, if I've been able to sufficiently specify the goal of a computational task, there will be a few or at least one sensical implementation, and any competent* programmer will eventually converge on one. Furthermore, when this implementation is shown to another competent* programmer for review, for the most part they'll mutter "yeah... OK..." and although they may also mutter "oh... cool" they wouldn't doubt they wouldn't have been able to eventually do it themselves (aside from the use of any abstract algorithm they weren't aware of*).
OTOH, if I ask for a new kind of mechanical lock with a special feature, a physical implementation may or may not exist - and if it does, most locksmiths or lock designers, perhaps generations of them, will not imagine it. But one does, and all the others look at it and go "...ohhhhh..." with the sense of seeing genius at work. That "noninevitability" (and thus nonobviousness) makes it perhaps worthy of a patent, whereas the computational task, being inevitably solvable, is essentially obvious.
*or maybe we need "groups of programmers" to ensure all skill of the art is being applied