After talking to Ilya and Tabrez we found the problem.
It turned out that the error message was misleading, and that it actually meant "auto-scale job failed to perform scale action". According to Ilya this is fixed (but not deployed)
I've tried to scale manually and got the following error:
The certificate with thumbprint XXXXXXXXXXXXX was not found.
A few days ago I've changed the SSL certificate thumbprint directly on the configuration tab of the Cloud Service, and then deleted the old certificate. This was reflected correct on our website. But we was also using this certificate for Remote Desktop. The running instances already had the old certificate installed, but Auto Scale was not able to install this certificate on new instances.
Thanks to Ilya and Tabrez for helping... great support.