As somas MD5 definitivamente devem coincidir. Eu baixei openssh-server_5.5p1-6+squeeze2_amd64.deb
e recebi o seguinte:
% md5sum usr/sbin/sshd
ba856dce069acadff587ca95e8e63551 usr/sbin/sshd
que corresponde ao openssh-server.md5sums
colado. Eu sugiro que você reinstale o pacote.