Double or triple check your API version. The response you are getting is exactly what you get with EntityDefiniton when you use API v31.0 or earlier.
SOAP Tooling API query to https://na87.salesforce.com/services/Soap/T/31.0/00D300000000001
Request
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:urn="urn:tooling.soap.sforce.com">
<soapenv:Header>
<urn:SessionHeader><urn:sessionId>00D30000000023456!AQ0AQIoLpcG6nREALSESSIONIDh9tFHVRr0iM3Q2iej8UZvlDNjKN</urn:sessionId>
</urn:SessionHeader>
</soapenv:Header>
<soapenv:Body>
<urn:query>
<urn:queryString>Select Id,QualifiedApiName,KeyPrefix from EntityDefinition where KeyPrefix = '001' limit 1</urn:queryString>
</urn:query>
</soapenv:Body>
</soapenv:Envelope>
Response
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:sf="urn:tooling.soap.sforce.com" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<soapenv:Body>
<soapenv:Fault>
<faultcode>sf:INVALID_TYPE</faultcode>
<faultstring>INVALID_TYPE: sObject type 'EntityDefinition' is not supported.</faultstring>
<detail>
<sf:InvalidSObjectFault xsi:type="sf:InvalidSObjectFault">
<sf:exceptionCode>INVALID_TYPE</sf:exceptionCode>
<sf:exceptionMessage>sObject type 'EntityDefinition' is not supported.</sf:exceptionMessage>
<sf:row>-1</sf:row>
<sf:column>-1</sf:column>
</sf:InvalidSObjectFault>
</detail>
</soapenv:Fault>
</soapenv:Body>
</soapenv:Envelope>
Same thing against v32.0.
Response
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:sf="urn:tooling.soap.sforce.com" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<soapenv:Body>
<soapenv:Fault>
<faultcode>sf:INVALID_FIELD</faultcode>
<faultstring>INVALID_FIELD:
Select Id,QualifiedApiName,KeyPrefix from EntityDefinition
^
ERROR at Row:1:Column:28
No such column 'KeyPrefix' on entity 'EntityDefinition'. If you are attempting to use a custom field, be sure to append the '__c' after the custom field name. Please reference your WSDL or the describe call for the appropriate names.</faultstring>
<detail>
<sf:InvalidFieldFault xsi:type="sf:InvalidFieldFault">
<sf:exceptionCode>INVALID_FIELD</sf:exceptionCode>
<sf:exceptionMessage>Select Id,QualifiedApiName,KeyPrefix from EntityDefinition
^
ERROR at Row:1:Column:28
No such column 'KeyPrefix' on entity 'EntityDefinition'. If you are attempting to use a custom field, be sure to append the '__c' after the custom field name. Please reference your WSDL or the describe call for the appropriate names.</sf:exceptionMessage>
<sf:row>1</sf:row>
<sf:column>28</sf:column>
</sf:InvalidFieldFault>
</detail>
</soapenv:Fault>
</soapenv:Body>
</soapenv:Envelope>
Then it starts working from v33.0 onwards:
Response
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns="urn:tooling.soap.sforce.com" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<soapenv:Body>
<queryResponse>
<result>
<done>true</done>
<entityTypeName>EntityDefinition</entityTypeName>
<queryLocator xsi:nil="true"/>
<records xsi:type="EntityDefinition">
<Id>4ie1W00001000GkQAI</Id>
<KeyPrefix>001</KeyPrefix>
<QualifiedApiName>Account</QualifiedApiName>
</records>
<size>1</size>
<totalSize>1</totalSize>
</result>
</queryResponse>
</soapenv:Body>
</soapenv:Envelope>