After setting up a new server with Ubuntu 12.04, I discovered that duplicity was unable to perform backups. The first problem was the missing ssh-backend. The package python-paramiko must be installed in order to use ssh-servers as backup target.
The second pitfall is a bit tricky, because of the confusing error message:
BackendException: ssh connection to server:22 failed: [Errno -2] Name or service not known
dpkg -i duplicity_0.6.19-0ubuntu1_amd64.deb