Edit History

También puede ser que lo estés subiendo doblemente comprimido, y por eso te lo detecte como no válido. Es decir, prueba a descomprimirlo el archivo zip del tema y ver si tienes otro zip dentro con el tema en sí, a veces los empaquetan así.

Otra posibilidad es que te hayas descargado el archivo para una versión diferente de Prestashop (por ejemplo, para la 1.6 y tengas la 1.7, o viceversa).