I had the same problem with a site on Network Solutions in fact. My gut feeling is that it is a NS problem because the site worked on other environments flawlessly. We were not able to track down the problem and NS didn't seem to be very helpful.
Good luck with getting error logs because that was a problem on the site I worked on. They didn't appear to be generated in the location that was indicated by the control panel.
Let me know if you find an answer.