更新Google Play服务后，应用程序将无法安装（8.1至8.3）(App won't install after updating google play services (8.1 to 8.3))

In my build.gradle I have:

compile 'com.google.android.gms:play-services-wearable:8.1.0'
compile 'com.google.android.gms:play-services-fitness:8.1.0'
compile 'com.google.android.gms:play-services-gcm:8.1.0'

and everything works like a charm.

When I change services' version to the latest 8.3.0, I get something like this:

Installing com.example.app
DEVICE SHELL COMMAND: pm install -r "/data/local/tmp/com.example.app"
    pkg: /data/local/tmp/com.example.app
Failure [INSTALL_FAILED_CONFLICTING_PROVIDER]


DEVICE SHELL COMMAND: pm uninstall com.example.app
DELETE_FAILED_INTERNAL_ERROR

My SDK is up to date, Android Studio alerts me of the newer version and my device's services version is 8.3.01

Am I missing something? I didn't find anything in the changelog and I'm stuck with this for hours...

EDIT - solution is simpler than you may think

I wasn't expecting this as I didn't even have my older app version installed, but some data was still there. I just needed to install old, working version once again, clear the data, uninstall, and the problem is gone. All credits to Alex K and his answer.