Ao instalar o PHPBrew em uma configuração totalmente nova do ubuntu 16.04, a página de requisitos (que explica o php5) não é muito útil para iniciar as coisas sem problemas. Esta é uma configuração minimalista que você pode usar para instalar uma + variante padrão do php7 via PHPBrew
~$ sudo apt-get update
~$ sudo apt-get install php7.0 php7.0-curl php7.0-json php7.0-cgi
~$ sudo apt-get install php7.0-fpm autoconf automake libxml2-dev libcurl4-openssl-dev libssl-dev openssl gettext libicu-dev libmcrypt-dev libmcrypt4 libbz2-dev libreadline-dev gettext build-essential libmhash-dev libmhash2 libicu-dev libxslt-dev
~$ phpbrew install php-7.0.9 +default+mcrypt+zlib+sockets+soap+mhash+fpm+openssl