Na verdade, foi apenas um problema com o PHP 7.0 e todas as suas dependências. Eu tive que adicionar o ppa para instalá-lo no 14.04, eles foram removidos com o upgrade, mas sua versão ainda era mais recente do que 16.04 repositórios oficiais e isso estava impedindo qualquer tipo de instalação relacionada ao PHP 7.0.
Eu removi o pacote php7.0-common e reinstalei tudo do zero, incluindo extensões etc. Parece que está funcionando bem agora.
Infelizmente eu não encontrei uma maneira de fazer o downgrade dos pacotes, pois eles estavam dependendo um do outro, então o downgrade da versão estava falhando por qualquer coisa que eu tentei (php7.0, php7.0-common, etc.)