I'm really posting this question so that others searching for the answer can find it.
Scenario: WCF Service: Has worked fine at some point but currently is returning 403 errors. The web.config looks fine as far as I can tell. This machine has set the web.config to disable transport and message security and is using BasicHTTPBinding.
When I call it with my client generated from the Service Reference in Visual Studio, I get a 403 error. The error indicates there is some problem with the authentication, but as far as I can tell there is no such problem.