Судя по всему произошло следующее:
1. Почему-то я подписывал этот отдельно взятый apk дебажным сертификатом. Без понятия, как такое могло случиться, если до этого я уже много раз подписывал другие apk своим рабочим сертификатом (Eclipse->Export...)
2. Почему-то гугл пропустил apk, подписанный дебажным сертификатом.
3. Тот дебажный сертификат давно потерян ибо софт переустанавливался, да и зачем хранить дебажные сертификаты.
Итог ясен: старый apk больше обновить нельзя. Придется выпускать новый, а старому сделать Unpublish.
