This is a separate issue. Remove AEAD and you don't interop. Add AEAD with my rule and you still don't interop. To improve the situation we need to twist the KEXINIT abstraction a bit more (no objections from me): IF a non-AEAD cipher is chosen AND there was no common MAC AND there was a common AEAD cipher THEN re-compute the cipher selection ignoring all non-AEAD ciphers.
Ugh. This is starting to get complicated.