ssh wird oft auf einem Nicht-Standard-Port betrieben. Mit ssh-copy-id gibt es jedoch ein bekanntes Problem unter Debian (auch aktuelle Versionen), sobald ein anderer Port als 22 verwendet wird. Das kann aber recht leicht umgangen werden:

ssh-copy-id "user@host -p 2222"

Oder man legt das ganze einfach in ./ssh/config entsprechend an, dann klappt das auch wie gewohnt…