This has just happened to me as well. Though the last time I updated the problem app was last year and I, too, have updated to v13.40. I have successfully updated other apps but the difference with the problem app is that I opted in to "Play app signing".
EDIT: Ignore the above, it was my mistake, I was using the wrong "#SignKeyFile:".
Lucian, you say you have multiple keystores, I would suggest you double-check that you are using the correct one because the error message you are getting is exactly the same as the one I received.