Maybe your learning rate is too high. I had some similar issues in relation to learning progress and more classes. If this is the solution, the reason for that is that gradient descent does not work properly an ignores local minima. Please let me know.