From Professional C#: 3rd Edition
I have found that (at least in my case) that you (may?) need to add PreAuthenticate code in order to get the SOAP Headers example to work. Otherwise, you will get an exception of "The request failed with HTTP status 401: Unauthorized".
I found this solution at: http://www.heybo.com/weblog/posts/245.aspx
Basically, you would need to add this code:
myService = new Service1();
myService.PreAuthenticate = true;
AuthenticationToken header = new AuthenticationToken();
Hopefully, this will save somebody some time and headaches.