This just started happening to me when I send emails from my msn email account from my Motorola Droid Razr Maxx. My first few days using this phone and sending email from that account, it did not happen. Now it is. It may have coincided with the phone software upgrade, though I can't be certain.
Currently running Android 2.3.6
The only place where the gibberish shows is where my name should be in the email. The recipients indicate my email in their inbox shows my name as Gbkshdishwlfhw Skhfaoislwddlash. It always shows for everybody in the same exact gibberish. It also shows in the body of the email something like:
Gbkshdishwlfhw Skhfaoislwddlash wrote:
I went to the accounts on my phone and set the nickname for my MSN account to my full name, as it was set to match the actual email address. This did not help.
ETA: that I checked the test emails I sent to myself from the phone using MSN to both my google and MSN accounts. The gibberish shows in both emails when viewed from my Android phone, however, when I go to my pc to pull up the emails from MSN and google mail, the gibberish is not viewed in the MSN viewed version in the inbox view or body of the message as described above but it is present in the google pc version. So perhaps the issue is with google programming and contacts versions.