If you rez a new prim (like the default cube) and try to call llSetKeyframedMotion on it, you'll get the following error:
Error, failed to play animation. Does your linkset exceed the complexity limit for keyframing?
This error is very vague and misleading. There should be more internal checks so a more specific errors can be given, or in this specific example the sim should update the object as I'm about to explain.
In this case the error happens because the fresh prim is under the old Prim Equivalency system. The current workaround is to make some change to the prim to bring it under the new PE system.
For example, adding a specular texture to the prim will fix the error. Changing the prim's physics shape to Convex Hull will also fix the error. I imagine the sim might be able to update the object's physics shape type when llSetKeyframedMotion is called, but I don't know all the possible side-effects.