CommonsWare is right, but in my opinion this is a (bug)poor way to say: "The apk installed on the device is signed with a different certificate then the new one you are trying to install".
This is probably a new bug since in the past it used to ask whether or not to uninstall the app from the device due to wrong certificate.
The solution as painful as it may be would be to uninstall the app it manually.
Also what we've done for the sake of team development, we added the debug keystore to our repository, and point gradle to use it like so:
android {
...
signingConfigs {
debug {
storeFile file("../certificates/debug.keystore")
}
}
...
buildTypes {
debug {
signingConfig signingConfigs.debug
}
}
...
}
And now when passing devices between team members, we all use the same debug certificate, so there is no issue. :)