Why can't I use scp after having set up ssh-copy-id
Solution 1:
Because you are using sudo on your second command, but not on your first.
Your first command is run by the your user, the second is run as root.
You need to either clean up the known keys of the root user (if you are sure that the host keys HAVE actually changed), and run ssh-copy-id again with sudo, or you skip the sudo if you don't need it.