Animator.Update High CPU Usage on Unity 5 resulting in bugs on Android

I have upgraded a project to Unity 5 (from 4.6) but it is running extremely slow on Android specifically.

The Animator.Update uses over 50% CPU power and spikes up to 60%. I've checked the same project in Unity 4.6 and it is only using an average of 1% with some spikes (<1 second) of ~12%.

The Animator also gets stuck in some states on Android. My menu works with transitions using animations, but it gets stuck in some menu's because the animator doesn't change states.

The game works perfectly fine inside the editor (still 50% Animator CPU usage, but not noticeable on my PC) no skipping states or anything. Problem is the game is now completely broken on Android because of the Animator behaving strangely.

Animator performance on Android Unity 5.0.

Animator performance InEditor on Unity 5.0 Upgraded project, same Animator.

So my main question is: Is there something i am doing wrong or is it on Unity their side? Everything works perfectly fine inside the Editor Play and also on a Web Build (both run at 60+ fps) It's just that the Android build is completely broken. Am i doing something wrong or should i wait on a fix from Unity?

My Android devices are a Nexus 7 (2013) and a Nexus 5 by the way.