Well it turns out my problem was two-fold. First of all, the webservice I was attempting to access via lwp was url redirecting multiple times. I wasn't handling this properly. Secondly, as part of the headers I was ignoring any cookies that the server set. I didn't think they were necessary, but it turns out they were. I guess ASP.net requires accepting a sessionID cookie.

Once I properly handled both of those items I was able to receive successful results. Thanks for the help printing out the headers.