Installed Percona-Toolkit, but no sign of xtrabackup
It turned out to be an issue with our Proxy Server, blocking downloads from percona.com

Running sudo apt-get update revealed that every connection to percona.com 'failed', and so I got that added to the approved list, and after that it installed fine.