Exchange Server 5.5

My company has 15 regional offices throughout the United States. In order to connect to our Mail server and Mainframe, they are connected through a 56k frame-relay circuit. Lately, some, not all offices, have complained about the length of time ittakes for them to either open an attachement or get their mail. I am wondering if this is a circuit issue or not. Also, do you have any ideas on what I should be checking for on the server in order to speed up the e-mail process so it does not hang up?

Thanks,
Paulo