I'm not 100% sure, but I don't think so. Simply re-signing the same intermediate certificate (by the CA) with a better hash should allow the new intermediate cert to be a drop-in replacement, as the private/public keys didn't actually change.

You can probably download their latest intermediate certificate or bundle (https://www.startssl.com/certs/) to resolve the error.

Notice how their current intermediate cert has a SHA256 hash, yet they don't offer an "old" intermediate cert which would supposedly be required for older certificates.

No, because their intermediate is the same public key, resigned with SHA2. So you just need to update it in your chain.

I belive the problem was the signature on the intermediate. The same intermediate has probably been signed again with sha2. Or maybe it was cross signed somehow...

I just replaced the intermediate cert and the warnings went away.

You guess correctly.