this seems to be caused by switching from JDK 1.6 to JDK 1.7. Instead of sticking to JDK 1.6 (which is not an option in some cases), I recommend to create a small script for creating the signed&aligned apk based on http://developer.xamarin.com/guides/android/deployment,_testing,_and_metrics/publishing_an_application/part_1_-_preparing_an_application_for_release/
# First clean the Release target.
msbuild.exe HelloWorld.csproj /p:Configuration=Release /t:Clean
# Now build the project, using the Release target.
msbuild.exe HelloWorld.csproj /p:Configuration=Release /t:PackageForAndroid
# At this point there is only the unsigned APK - sign it.
# The script will pause here as jarsigner prompts for the password.
# It is possible to provide they keystore password for jarsigner.exe by adding an extra command line parameter -storepass, for example
# -storepass <MY_SECRET_PASSWORD>
# If this script is to be checked in to source code control then it is not recommended to include the password as part of this script.
& 'C:\Program Files\Java\jdk1.6.0_24\bin\jarsigner.exe' -verbose -sigalg SHA1withRSA -digestalg SHA1 -keystore ./xample.keystore -signedjar ./bin/Release/mono.samples.helloworld-signed.apk ./bin/Release/mono.samples.helloworld.apk publishingdoc
# Now zipalign it. The -v parameter tells zipalign to verify the APK afterwards.
& 'C:\Program Files\Android\android-sdk\tools\zipalign.exe' -f -v 4 ./bin/Release/mono.samples.helloworld-signed.apk ./helloworld.apk
The important part is to use the parameters -sigalg SHA1withRSA -digestalg SHA1 which force JDK 1.7 to use the expected digest algorithm (instead of SHA-256 which seems to be the default in JDK 1.7 and is not accepted by all Android versions).
Note that you can find the msbuild location with
$dotNetVersion = "4.0"
$regKey = "HKLM:\software\Microsoft\MSBuild\ToolsVersions\$dotNetVersion"
$regProperty = "MSBuildToolsPath"
$msbuildExe = join-path -path (Get-ItemProperty $regKey).$regProperty -childpath "msbuild.exe"