For the record
I think I got it.
The Web.Config from the service does not have the binding information.
I placed this info in it, and voila!
<bindings>
<basicHttpBinding>
<binding maxBufferPoolSize="2147483647" maxBufferSize="2147483647" maxReceivedMessageSize="2147483647" messageEncoding="Text">
<readerQuotas maxDepth="2000000" maxStringContentLength="2147483647" maxArrayLength="2147483647" maxBytesPerRead="2147483647" maxNameTableCharCount="2147483647" />
</binding>
</basicHttpBinding>
</bindings>
Note here that the binding did not have a name specified.