@IgorMinar @petebacondarwin @matsko I was able to reproduce the issue finally:
http://plnkr.co/edit/I57CKjdHBZeqEHtZ4Bn9?p=preview

In this example, ngClass applies 3 classes to the element. After a two second timeout, ngClass removes one of the classes. But if ngAnimate is declared as a dependency, ngAnimate removes all 3 classes.

But only if any of those classes has a transition duration.

The place where this happens is during ngAnimate's cleanup phase:
element.removeData(NG_ANIMATE_STATE)

This was maddening to track down :)