Here's an easily misinterpreted error when consuming a WCF service that's hosted in IIS (vs. a self-hosted service):
The content type text/html;charset=iso-8859-1 of the response message does not match the content type of the binding (text/xml; charset=utf-8). If using a custom encoder, be sure that the IsContentTypeSupported method is implemented properly.
This typically happens with a mis-configured service. Anything that will result in a configuration or compile error will be returned as a 500 error by IIS. This error renders as HTML, and thus is the wrong encoding and not recognized by the client channel stack. Any exceptions thrown once the service code executes will result in a properly formed FaultException, which traverses the channel stack just fine and can be handled by client code.
To resolve this error, double-check the service's configuration file and make sure the service compiles. Test by bringing it up in a browser that has "Show friendly HTTP error messages" disabled.