Lots of different reasons why the key could of changed, did you reinstall sshd on your desktop. Did you install/reinstall OS? Was some other box that you had ssh'd too have been on the same IP at one point?
If your sure your connecting to the correct box, then as suggested just remove the OLD host key from your laptop for the desktop and then you won't get the error. This shows that the desktop is now atleast listening on 22
Or maybe desktop is not listening still, and your connecting to some other box that now has that IP and is running sshd - that too would explain the host key mismatch.
What did you do to correct that, did you edit the config file with the bad allowuser statement? Or just the start/restart of sshd?