Ah, okay, I was more focused on the user-controller relationship and not on the controller-processor deal.
If a company legally holding private data (i.e. a controller) gets a different subcontractor (a processor), they do not need new consent from the user; and the controller is still fully responsible for the data privacy.
In your example, you're a processor who operates the data with controller's authorization (let's avoid the word "consent"; this is a quite specific term in context of GDPR with a different meaning) - and they are responsible for ensuring that you will safeguard this data properly, so they can't transfer data to you if they don't have solid guarantees about what you'll do and not do with the data they're responsible for.
And the particular situation seems reasonable to me. You do not need to ask all SaaS customers for some action; as your links directly quote ".. or general written authorisation of the controller" i.e. your agreement can specify (if your customers are okay with that) that you're allowed to use other processors and change them. You do have to inform them about such changes (just as you informed them about the current subcontractors touching their data before they signed up, right?). If you change from Mailgun to Postmark, all you have to do is to send a notification to all your SaaS customers, and nobody is going to cancel over that. On the other hand, if you change from Mailgun to NigerianPrinceMailings Inc., then they might reasonably want to decline, so that's why the notification is required.