Several users have reported issues that arise when an older version of protobuf is installed.
TensorFlow requires (and uses a copy of) protobuf-3.0.0a4. However it seems to be conflicting with your installed version (perhaps due to how the PYTHONPATH environment variable is configured on your system?). Can you try uninstalling the python-protobuf
package if it is installed, and then seeing if TensorFlow starts correctly?
Some users have had success when using a virtualenv. For instructions on installing TensorFlow into a virtualenv, see the getting started guide.