Yeah, I've experienced the same thing, though not consistently enough to be able to learn any pattern as to what kind of models MayaCloth will tolerate.
First: A couple of quick things to check (you probably have already, but just in case):
1) Check the normals on the collision object... make sure they point out.
2) Watch the collison offset... make sure it's not too high, and the collision depth can really screw you up, too... the correct depth obviously depends on the type of object.
3) Try exporting the object as an .obj and then re-importing.
Assuming that none of the above helped... I've taken Maya primitives and used them to fashion rough, quick and dirty copies of the original object, and used the rough copy as the collision object instead. If you're doing IK, for example, the roughed out collision object can be deformed by the same IK chain you're doing your other animation on--so no remake of the animation is necessary... furthermore, you can frequently get away with a really low rez object for collisions without anyone being the wiser. (It's annoying, you shouldn't HAVE to do it, but it's a work-around...)
Good luck...