Если проблема не у всех, а у некоторых клиентов. То узнайте когда последний раз менялся пароль у пользователя, у которого запрашивает пароль. Попробуйте сменить пароль и попробуйте перелогиниться. Еще вариант, проверьте не используется ли прокси для IE, если используется, разрешите обращаться напрямую до вашего Exchange, включая autodiscover или просто отключите прокси на время проверки. Если это не поможет дайте знать будем разбираться :)