Am I missing something? It sure looks to me like either OpenSSH or
Ubuntu (whichever one decided to do this) gratuitously breaking interop
by desupporting a REQUIRED algorithm.
"MUST is for implementers".
It doesn't apply to people setting security policy, whether for themselves, their entire organization, or the defaults for everyone running an operating system they distribute. For most major Linux distributions with which I am familiar, it is still _possilble_ to configure support for ssh-dss, but it is not the default, and has not been best practice for some time.
Also, AFAIK, servers typically advertise public key algorithms (for keyex) for which they actually have keys. That host, if recently installed, almost certainly does not have an ssh-dss key.