How much to concentrate on patching?

There’s an interesting, if currently brief, discussion about the Verizon patching article going on over at the Security Catalyst Forums. Succinctly, Verizon’s study demonstrates that patching isn’t the be-all end-all of security measures. (Who’d have thunk it?)
I’m not sure precisely where I stand. I disagree somewhat with Andy Willingham’s position, although it may be because I also disagree with his use of the word 0day. No patching will save you from a 0day, since by definition there *are* no patches for those. (Yet.)
My own experience in the last year or so has been that *every* compromise has been for reasons other than no patches. I will stipulate in advance that we’ve actually had very few recently, at least in my group, but none would have been prevented by patching, since there is no patch for human stupidity. All of them have been weak passwords on system accounts, so what would have helped us would have been a strong password and auditing policy. To counter that, the first time I really let Nessus loose on our network, I discovered (and pwned) a Windows machine that had not been patched in over a year. That machine was somewhat protected by a host-based firewall, but anybody on our networks could have seen it and done the same thing I did. (Yes, it’s getting patched regularly now, and yes, I’m fairly sure nobody else *did* do what I did.)
I lean more towards Randy Armknecht’s position: patching is great as part of a bigger security strategy, although I wouldn’t be so dismissive as to say, “Nothing new here.” If it’s worth saying something once, it should be worth repeating it, and Verizon, at least, have done a fairly comprehensive study to back up the repetition.
This seems a very Windows-centric discussion. The unfortunate part of desktop Linux installations is it’s difficult to keep all your machines patched, or to ensure that patches are installed at appropriate times. It took me about 3 weeks to track down and cause to be patched all our Debian-based boxes with vulnerable SSH host keys. Granted the time could have been drastically reduced if I was actually allowed to concentrate more time on security issues (it only took five or six hours, counting time updating old machines and notifying clients, then beating a few up into actually updating), but the time could also have been drastically reduced if the vendor made that sort of thing at all easy.
Furthermore, as a colleague at the UofT points out, sometimes patching is worse than the alternative. How many times have you applied the latest patch, only to have to apply a patch for the patch? Hands up, everybody who’s lost time over that. What about when a machine is rendered unusable as a result of a patch? There was a particular MacOS 10.4 patch that checked for sufficient free disk space before installing, but got the figure wrong – so if your free disk space fell into a certain range, the patch would half-apply then fail and you got to figure out how to make your machine go again.
At any rate, I wonder how much time it’s worth spending on ensuring a decent patch strategy, and how much time one should spend on other issues.