I am having the same issue sending an SMS message from sp_send_dbmail through Nextel. The sender and subject are fine, but the body is a mish-mash of text.

Did you...