Exchange/Outlook character set?

A few users are occasionally getting emails that say this...

This message uses a character set that is not supported by the Internet Service. To view the original message content, open the attached message. If the text doesn't display correctly, save the attachment to disk, and then open it using a viewer that can display the original character set.

The attachment is a .txt file that contains the original email message. We have an Exchange 5.5 server, and Outlook 2k. Any ideas what is causing this, or how to fix it?
The email that was just forwarded to me asking about this was from Verizon.net, which I also use, so I sent a test email to myself using their webmail service, and it came through fine...