I think that software patents could be a bit more palatable if they also had to provide source code that was proven to compile and work as describe in the patent. As it stands right now, source code is not necessary, and only a vague description of what the functionality is necessary for software patents. That means, even if somebody else finds a better algorithm for doing what is covered in the patent, then the patent might still apply.
This very much stifles innovation. Let's say somebody invents a wood chopping machine and patents it. Now I discover something that is slowing their machine down, or making it unreliable. If I find out a solution to that, I can patent my fix and start selling a better wood chopping machine. With software, if somebody patents the idea of compressing a video, and I come up with an algorithm that compresses it at 10 times the speed while achieving the same end result, then my algorithm would probably already be covered by the existing patent.