David,
Can you please provide a few more pieces of information? First, have you enabled security on your services? If so, please let us know what type. Second, how are you accessing the service (through a firewall/DMZ, or internally). Finally, what is your local security policy setting for Network security: LAN Manager authentication level? We recommend that it be set to "Send LM and NTLM only".
Thanks,
Eric Miller
Esri Product Engineer