Your 56k frame relay does not really run at 56k. The CIR (or Committed Information Rate) for a 56k frame relay circuit is 32k. While this speed is okay for simply mail messages, it will cause problems with large file transfers.
Outlook acts as afront end for Exchange. Attachments that appear in a mail message are actually stored in Exchange. When a user opens a large attachment, such as a large Excel spreadsheet, Access DB, or Powerpoint presentation, all those bits are then crossing you frame relay connection at 32k/s or less. It is the same as if you were downloading a large file off the Internet through a modem. Think of how long it would take to download a 1 meg file through that connection. Also keep in mind that others in theoffice are also using the same connection simultaneously, thus futher decreasing bandwidth.
Due to the much higher price of fractional T1 (256k to 1.5mb), perhaps you could look into VPN solutions using DSL. Another solution would be teach your users to copy and paste through shared folders on your network, rather than send attachments. This would keep Outlook from freezing during file transfers. Zipping large files is also another way to go.
Probably not what you want to here, but answer 1 is right... your connection is too slow.