StartSSL have sha2 intermediates nowdays. https://www.startssl.com/certs/class1/sha2/pem/

I guess using these will still require a re-issue of existing leaf certificates, so the signature matches the sha2 intermediate?

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.

Actually it seemed work by just updating the intermediate chain cert. Still need to try to re-issue leaf certs that are actually signed with sha1...

The expiration date of the intermediate doesn't matter.