yeah.. do you have symantec running? that also has size limits set for e-mails. or you could always go to AD users and computers and go to the user properties and go to one of the exchange tabs (can't remember which), and see if limits are set there too.
EDIT: who knows, it may be the other person's e-mail server that's not letting it go through do to the size of it.