Internet sharing over a WAN

Our company recently upgraded from a shared ISDN connection to DSL. The DSL line comes through our headquarters and into a cisco 1600 series router, then a hardware firewall and finally a network hub. Our remote stores connect to us via slowish 56k Frame Relay lines. Rather than routers we use FRAD’s as the gateway devices at the remote stores. The headquarters uses a Fractional T1 running at 256k incoming. Here’s the problem: since the upgrade the remote stores have noticed a DECREASE in internet performance (eg mail server time-outs sending larger attachments) Has the increased traffic from the DSL congested our pipes? Any suggestions? Perhaps replacing the hub(s) at headquarters with switches would help?