According to the Xamarin documentation, building an Android package in Debug or Release modes still signs the package with a new debug signing-key (cryptographic identity). To properly sign you Android package, you need to set the Build configuration to "Release" and then go to Tools -> Publish Android Application. This will not publish your app in Google Play. It will let you sign your app with your signing-key (or create a new one) and it will build the package. Here is a link to a documentation article for reference: Xamarin - Preparing an Application for Release
. Search for "Signing the APK in Visual Studio".
You should do this every time you release an app or an app update to avoid signature conflicts. Otherwise, the Xamarin plugin creates a new debug signing-key for your app every time and the update cannot be applied to an older version.
Let me know if this information helps.
Check out the Telerik Platform - the only platform that combines a rich set of UI tools with powerful cloud services to develop web, hybrid and native mobile apps.