Hey Alex, you could try running something like Fiddler to capture the traffic. This would show us information like what user they're trying to authenticate against as well as what user they're trying to get autodiscover settings for.
Also, in the domain's settings make sure you have the proper autodiscover protocols enabled for the user you're testing with and that they are enabled for that protocol.
Larry Duran
Software Developer
SmarterTools Inc.
www.smartertools.com