An error occurred when verifying security for the message

When I try to call a WCF service I am getting the following message "An error occurred when verifying security for the message."

When I remove the custom authenication the service works no problem. I can't figure out though what I have misconfigured in my web.config. Any insight would be appreciated.

  <system.serviceModel>
     <services>
        <service behaviorConfiguration="NAThriveExtensions.nableAPIBehavior"
          name="NAThriveExtensions.nableAPI">
           <endpoint 
             address="" 
             binding="basicHttpBinding" 
             bindingConfiguration="basicHttpBinding_Secure"
             contract="NAThriveExtensions.InableAPI">
           </endpoint>
           <endpoint 
             address="mex" 
             binding="mexHttpsBinding" 
             contract="IMetadataExchange" />
        </service>
     </services>
     <behaviors>
        <serviceBehaviors>
          <behavior name="NAThriveExtensions.nableAPIBehavior">
            <serviceMetadata httpsGetEnabled="true" />
            <serviceDebug includeExceptionDetailInFaults="false" />
            <serviceCredentials>
              <userNameAuthentication 
                userNamePasswordValidationMode="Custom" 
              customUserNamePasswordValidatorType= "NAThriveExtensions.Authentication, NAThriveExtensions" />
            </serviceCredentials>
          </behavior>
        </serviceBehaviors>
     </behaviors>
     <bindings>
       <basicHttpBinding>
         <binding name="basicHttpBinding_Secure">
           <security mode="TransportWithMessageCredential">
             <message clientCredentialType="UserName"/>
           </security>
         </binding>
       </basicHttpBinding>
     </bindings>
  </system.serviceModel>

This ended up being an problem on the consuming side, not with the service itself. Software AG's webMethods 8 was consuming this server but there was no Security Handler added to the service so the credentials were not being added to the header thus resulting the in the aforementioned error.