what admin activity happened between the rebuild and when this started? any category permission changes? if there was a week delay, then something in between may have changed it. or was it only a week later that the moderator tried? did you look in the staff log to see if any category or group permission changes occurred that could have affected this?
i also wonder if the recently enabled newfangled simplified category creation thing inadvertently affected some configurations 