Out look problem

Users on the network begin to report problems of messages from Outlook indicating it is sporadically losing connection to the (local) Exchange server. The only change in the environment was a switch in Internet providers and an installation of a new DSL modem/router. How would you go about diagnosing the problem(s)?