Trusting the root user is different from trusting everyone with shell access to that machine. Only root (or a process with the appropriate capability) can bind to port 22 because it's below port 1024. Normal users can bind to port 2222. So now $EVIL_USER puts "@reboot /home/$EVIL_USER/bind_port_2222" in his crontab, or some such other method of getting to port 2222 before the ssh daemon.
This is mostly mitigated by the fact that $EVIL_USER can't read the host private keys which means that the impersonation will be detected by anyone who has the host in the known_hosts file, but that only counts for ssh, and assumes you've connected to the host previously. If you're running something like DNS or FTP on a multi-user machine, using a non-privileged port is a Bad Idea.