El problema aquí es que tu .APK en realidad esta firmado pero en este caso probablemente esta usando información de otro certificado, probablemente uno antiguo, por esta razón no te permite subir el .apk a Google Play Store.
Vuelve a construir tu proyecto, firmarmediante Clean Project
, firma nuevamente el .APK y cárgalo nuevamente.
Si es una actualización y usas un .jks, asegura seleccionar el correcto certificado.