Problemas para compilar apk release final y google play

[wolfran_hack]

Muy buenas miembros del foro, como veran en el titulo estoy teniendo problemas para compilar una versión release final firmada para el google play, al compilar Control+F9 y Shift+F9 no me genera el archivo final apk en la carpeta release, tengo que si o si hacer un debugging Control+Shift+F9 para que la genere, y me da el siguiente error:



La aplicacion no esta instalada en el mobil, por ende no comprendo el error, la so

Como se creo el archivo apk lo subo y google play no me dice nada, me lo toma como que esta perfectamente creado.

Se publica la apk y al instalar desde el google play da el siguiente error:

No se puede instalar la aplicación:

No se puede instalar "APP". Vuelve a interntarlo y, si el problema persiste, obten ayuda para solucionarlo. (Código de error: -504)

Alguna idea de solucionarlo?