I use mobile wallets exclusively. I assume Mycelium is safe, right? From all I've read about it here, it seems to be at least one of the preferred wallets.
And how about the one by "Bitcoin Wallet developers" for Android. That's one I saw on the app store, and it's one that comes up second when you search for "bitcoin wallet".
I think the issue is with Android itself. No one ever seems to give its overall security any thought. They just assume it's fine and press on.
Considering how much lucrative info is on the average phone these days there are going to be ever more attempts to gain nefarious entry into it.
And in this particular case the second problem is a 'feature' of the OS and it's exposing your data to google. I can't imagine their security is anything other than exemplary but you never know.