Mark Fussell discusses a common problem when using WSE 3.0 and Kerberos security.  He answers the following question:

I need advice with WSE 3.0 and implementing a web service that requires a Kerberos token. It seems that my simple web service and Windows client should be straight-forward but I’m not able to get past the error “Security requirements are not satisfied because the security header is not present in the incoming message."

   -Matt