Infelizmente, o protobuf3 não pode ser adquirido através do apt-get até o Ubuntu 16.10 (Yakkety Yak) . Então, você precisará atualizar para essa versão do Ubuntu primeiro ou obter a biblioteca de seu repositório git.
Após as instruções no link , instale um pré-construído a partir daqui link ou construa você mesmo a partir das fontes (se você quiser participar do esforço de desenvolvimento da própria biblioteca).