I've had Red Hat Enterprise Linux and Ubuntu products before, and occasionally they have "Service Packs". Essentially, some time the vendor decides "gee, we've shipped a lot of patches. Lets respin the CD". Apparently this isn't what Novell / SuSE do.
You see, when Novell / SuSE ship a "service pack", they helpfully stop all machines which don't have that service pack from taking any updates. And you have to go through a long winded "upgrade to the service pack" process (documented here, I used the "rug" method), after which you can once again resume normal service of getting patches.
So that's why my updates haven't been working for a while on my SuSE servers.