There are details lacking from your question -
How is the web service secured?
When you say it works using soapUI - how exactly? have you checked how the credentials were supplied to the service? could it be that the soapUI was running under a user with permissions for the service in question, and that this is why it works (similar to a BizTalk call working under NTLM authentication?)
As you're undoubtedly aware, to use Basic or Digest you simply have to provide the correct credentials in the send port and, assuming they are correct, and the web service is configured correctly, things should work nicely.
To test this carefully I would first make sure you are running whatever client (soapUI or custom test code) under a user that has no permissions to call service (assuming that is not the case already), make sure you know the credentials, and have succesfully called the service, with the right credentials, from another client (also prove that it fails if you provide the wrong password, for example), then use the same username/password combination in the send port.
by the way - it will also be useful to check the proxy settings; things can get quite confusing if it is the proxy that is rejecting the request and not the service as it happened to me on a few occasions.
in all cases HttpAnalyzer of Fiddler can be very useful in understanding what is happening following the traffic on the wire