Just a follow up to the previous posts of this thread, and things to be aware of when testing browser enabled forms...
After a lot of researching and testing, it ended up being a double-hop issue that I was dealing with.
By putting explicit authentication in the udx file and testing that; if it works and it previously wasn't, then that helps to clarify that the double hop issues exists.
Also following which, I moved the custom web service that I created to a WFE server rather than a separate server and after removing the explicit authentication, this also worked.
I was testing some browser-enabled form options and I kept having an issue with this. Of course we are looking into more secure security methodologies but these are good troubleshooting tips if you run into a similar issue.
--Adam