Clicking on category link yields error

On my install of WPMU one of my user blogs gets a strange message when we click on one of his categories.

Three of his posts are assigned this category yet when the link is clicked the “page not found” error comes up.

What causes this and how can I fix it?