Exchange 5.5: Undeliverable.

We’re having problems with emails with attachments. We got the notification from Exchange that says:

Your message did not reach some or all of the intended recipients.

The following recipient(s) could not be reached:

The content length of the message is too long for the recipient to take delivery

We recently added a firewall, changed our ip address and our ISP wondering if any of this is causing it. Some times it works and some times not.