[Zebestov]

Сертификат должен быть один и тот же. Проблема (насколько мне известно) может быть в 1024-битном сертификате, который Google Play когда-то грозился перестать поддерживать. Если же сертификат 2048-битный, то очевидно дело точно не в нем.