Exchange 2007 To/From Garbled Text

[slatecom]

After setting up an Exchange server, I have found that although I am able to send emails, when I check the test email using Hotmail, it appears that 9/10 times the "From" name appears fine when looking at the list of emails, but when I click to view the email, the "To" and "From" names are garbled and look like this: ???????. The actual message comes out perfectly fine.

Is this just a bug in Hotmail, or a problem with my Exchange server?
If it's a problem with my Exchange server, how would I go about fixing it?

Thanks!