By default, recent versions of OpenSSH don't employ DSS-based authentication. Some claim this is due to performance reasons (RSA encrypts faster, DSS decrypts faster) and others will point to vague discussions on security. It appears to be a preference by the maintainer.
It's not that the server refuses to use DSS. DSS is actually disabled in the client. To enable the use of DSS, create ~/.ssh/config containing the following line:
You shouldn't need to restart any service. The next time that you use your client, DSS authentication should work.