Por fim, consegui resolver o problema pesquisando o pacote no repositório do Ubuntu.
O php7.0-mbstring para o php 7.0.13 estava no repositório proposto que não estava na minha lista de fontes
Então eu editei meu sources.list em /etc/apt/sources.list adicionando
deb http://archive.ubuntu.com/ubuntu/ xenial-proposed restricted main multiverse universe
execute apt-get update
e, em seguida, apt-get install php7.0-mbstring
Funcionou bem!