Update from Salesforce support:
I checked with R&D regarding this, and they are releasing an enhancement to allow all modifiers in the next version of the API, which is 34 (Summer '15). -Shashank
Source
It appears that at the API level protected
isn't supported.
Extract from the Tooling API v32.0 WSDL:
<xsd:simpleType name="SymbolVisibility">
<xsd:restriction base="xsd:string">
<xsd:enumeration value="Global"/>
<xsd:enumeration value="Public"/>
<xsd:enumeration value="Private"/>
</xsd:restriction>
</xsd:simpleType>
Note the absence of protected
. It can't be returned, so it appears they send back private
instead.
You also see hints of this in the documentation for SymbolTable:

It does seem odd the protected isn't represented, as it is valid in Apex access modifier.