It turns out that it was a PhoneGap Build bug. The old certificates seem to have been cached. I deleted the application (in PhoneGap Build) and all my certificate configurations. I created a new application and a new certificate configuration with the last good distribution certificates that I had previously used when I posted the question.
The build was successfuly accepted from the Application Loader.
So this was a PhoneGap Build bug.