Software patents are actually defined in terms of a physical object, the medium on which it's stored. They often include magic phrases like "a computer readable memory device having stored thereon a computer program".
IMHO, the problem isn't with the physicalness of the invention. After all, in the end it's really the insight and effort that you're trying to reward. The problem, I believe, is that the USPTO has done a terrible job of encouraging insight and effort by granting vague and obvious patents which contain neither, and the only "insight" was in how to game the patent office.
Judging what's insightful enough to merit a patent is tricky, but the patent trolls rely exclusively on patents where anybody "skilled in the art" would tell you that it was too trivial to bother writing down. The trolls rely on the fact that judges and juries are not skilled in the art, and are easily confused. Even in this case, the judge who came to the correct conclusion ends up making it (IMHO) needlessly complicated:
He explicitly makes "obviousness" a matter of law, i.e. a thing defined by the details of previous cases, rather than the universal opinion of those who would have done precisely the same thing if presented with the same problem.