Cannot access WCF Rest service by hostname

Question

I have WCF Rest service that is hosted inside of a Windows Service. It works perfect when I access it via IP address, for example:

http://12.34.456.78:31333

but returns a 400 Error when try to accesss it via hostname, for example:

http://myserver:31333

I have turned on tracing but that has not given me any information. My configuration is below. Does anyone know what is going on here?

<system.serviceModel>
    <services>
        <service name="MyApp.MyService" behaviorConfiguration="RestBehavior">
            <endpoint address="http://myserver:31333" binding="webHttpBinding" contract="MyApp.IMyService" behaviorConfiguration="MyServiceEndpointBehavior" bindingConfiguration="RestWebHttpBinding"/>
            <host><baseAddresses><add baseAddress="http://myserver:31333"/></baseAddresses></host>
        </service>
    </services>
    <behaviors>
        <endpointBehaviors>
            <behavior name="MyServiceEndpointBehavior">
                <webHttp/>
            </behavior>
        </endpointBehaviors>
        <serviceBehaviors>
            <behavior name="RestBehavior">
                <serviceMetadata httpsGetEnabled="true"/>
                <serviceDebug includeExceptionDetailInFaults="true"/>
                <serviceCredentials>
                    <windowsAuthentication allowAnonymousLogons="false" includeWindowsGroups="true"/>
                </serviceCredentials>
                <serviceThrottling maxConcurrentCalls="1024" maxConcurrentInstances="1024" maxConcurrentSessions="1024"/>
            </behavior>
            <behavior name="">
                <serviceMetadata httpGetEnabled="true"/>
                <serviceDebug includeExceptionDetailInFaults="false"/>
            </behavior>
        </serviceBehaviors>
    </behaviors>
    <bindings>
        <webHttpBinding>
            <binding name="RestWebHttpBinding">
                <security mode="TransportCredentialOnly">
                    <transport clientCredentialType="Windows" proxyCredentialType="Windows"/>
                </security>
            </binding>
        </webHttpBinding>
    </bindings>
    <serviceHostingEnvironment multipleSiteBindingsEnabled="True" aspNetCompatibilityEnabled="True"/>
</system.serviceModel>

EDIT:

When I change the clientCredentialType to "Ntlm", it seems to work with Internet Explorer. Of course, this is not what I want as I have clients out there that depend on the Windows authentication.