Desculpem, mas talvez esteja havendo um outro problema.
Vejam, o twisted python web no Ubuntu 16.04, sua versão é a 16.0.1, portanto este erro de dependência foi causado por uma versão antiga, como o apt mesmo mostra.
Tudo indica então que o paulfilipe tem uma versão mais antiga instalada aí ou usou um PPA da vida para instalar uma versão mais antiga.
paulfilipe, você fez uma atualização de uma versão mais antiga do Ubuntu para o 16.04?
De qualquer maneira, eu aconselharia a remover a versão antiga do twisted python web, no caso a versão 15 e depois instalar a versão 16 oficial dos repositórios do Ubuntu 16.04.