Sorry, the package name is protobuf-compiler without the lib, my bad.
sudo apt-get install protobuf-compiler