Então eu enviei um relatório de bug e a resposta foi esta:
You're not supposed to have xserver-xorg-input-libinput installable, that's not possible
because it's bound to the server input ABI
install xserver-xorg-input-libinput-hwe-16.04 instead
Instalando o pacote renomeado funcionou. Estes parecem ter sido renomeados recentemente, que é onde a confusão está vindo.