There have been some issues with old categories lately. For instance http://en.wikipedia.org/w/index.php?title=Category:Skiing_stubs was deprecated and it took over a month before all articles were removed. I'm pretty sure the last ones were actually null edited to force the category to become empty.
There are also some vandalism categories such as http://en.wikipedia.org/w/index.php?title=Category:You_are_gay_and_so_if_you_fucking_mother-Class_physics_articles
that kept having articles in them. Natalie fixed this as well by using nulledits. Still nulledits should not be required to purge old categories. It seems there is an issue in the jobqueue that caused these jobs to stall.
It might be that this was related to the problems with the lists of Special pages not updating. If that is the case it might be that the issue should now no longer occur, but that the categories simply didn't properly land on the jobqueue during the presence of the bug. This is speculation however.