I always bump into this problem of distorting a logo when I shrink it in illustrator. I have expanded the object and converted all outlines.
I tried 'simplify' and 'clean up' the anchor points, and I was holding down shift key when I resize the object.
I've looked at a few online forums and no one seem to ask this question so I'm not sure if I'm just doing anything wrong.
Things to check....
Is Align to Pixel Grid checked on the Transform Panel when the artwork is selected? If so.. turn it off unless you are create web images where it may be beneficial.
Is Scale Strokes and Effects Checked? (Transform Panel or Preferences in CS6, Only preferences in previous versions) If so, you may want to uncheck that option before scaling.
Beyond this, you'll need to define "Distort" far more than you have.