wow! sorry to see that going on... i don't have answer for you... but i'm just responding to help *BUMP this Thread! This should get a Addressed ASAP! Interested to know what the solution is... As I have yet to move on to Unity 4.0, but im sure I will in the near future. Best of Luck Resolving This Hopefully someone comes along with the right answer and you can show us another video of it working...
What variables drive the transitions in your mecanim graph? And what is setting those variables in code? If its based on the example mecanim projects, its probably input, in which case, it makes sense that remote players' mecanim animation states aren't changing (because you're only syncing position/rotation, and not the input that drives the mecanim graph variables).
Wish I could help, I think if no one responded with a Solution then you next step is to Hire Someone on the Commercial Work Forum: http://forum.unity3d.com/forums/31-Commercial-Work I'm sure you can find someone to help you for a small fee.
gotcha... well hopefully Unity Support can help. If not then try to hire fholm, I think if you have a credit card you can ask the consultant you are hiring to send you an invoice or something where you can pay without having to signup to paypal.
I believe they already gave you the reason "input based animations" you can get walk and sprint by just taking its "velocity" still its not enough so you can actually use a transparent game object that will be at X distance or X angle between the player and you so if(transform.position.x-XObject.transform.position.x == 10) walk else if(transform.position.x-XObject.transform.position.x == 15) run etc... this XObject MUST NOT have a rigid body and shouldnt need to render ^.^ not the best solution but should make it work
Here is an example of how to network mecanim: http://forum.unity3d.com/threads/164650-Released-Mecanim-Network-Example