When someone adds or removes a category from a page, the relevant category page changes. And when someone adds or removes an image from a page, the relevant image description page changes, due to the list of file links.
Cache updates for these changes are handled by LinksUpdate::invalidatePages(). However, this function does not update the HTML file cache (i.e. $wgUseFileCache=true), and it does not purge Squid. Thus, anonymous users see the old versions of categories and image description pages after an edit is made.
The fix is made more complicated by the fact that neither of these updates should be done in the same transaction as the main link update. The link update transaction locks a lot of rows, and needs to be closed off as soon as possible.