Como mencionado pela steeldriver, o pacote não está disponível até 16.10.
Uma opção é criar manualmente a partir da fonte ( github )
Uma segunda opção seria obtê-lo de um ppa de terceiros
sudo add-apt-repository ppa:aguignard/ppa
sudo apt-get update
sudo apt-get install xcb-util-xrm