I was also worried that the problem was related to certificates or obscure properties that would take days to solve, but Fiddler was a vital help. I had a 3rd party app which made the REST calls successfully, but my app was failing. I made a couple of calls in the working app and then in mine and I compared the traffic in Fiddler. I had to squint a bit, but eventually I noticed that my HttpWebRequest.Host property was different, and adjusting it to match the working app's value fixed my problem. So it was a subtle error which produce a frighteningly misleading symptom.
Fiddler couldn't unscramble to the HTTPS traffic at first, but there is an option you can switch on and then it makes and installs a fake certificate, then you can see what's happening. It's a great tool. This is the first time I've directly make REST calls, and I must say I admire the brain-dead simplicity of them. However, I'm not sure why I would use REST over old ASMX if I wanted the world to consume my API. Greg
