We had a similar problem with documents, but not categories.
Does your workspace name contain any uppercase characters? If so it may be this that is causing the problem. We managed to solve our problem by renaming the workspace, though I don't reckon that is supported/recommended by Microsoft.