This topic had been posted previously before, but i can't find it anymore.
Anyway, whenever I shrink a vector of somewhat complex shape (not just a circle or square, but lets say a logo), then enlarge it again, it totally distorts. I've tried turning off 'snap to pixel grid', and trying it with and without scale strokes/effects (even though i have no strokes/effects) and still no improvement.
I think maybe you are working too small.. Although Illustrator is a vector based software, there is a limit to how close you can have two points. So if you reduce a complicated logo to a hundred microns the software will only have so many 'points' to place each vector point, therefore it will reposition them giving your logo a distorted look when you enlarge it again. Have a look at what size the document is, enable your rulers too.
Hope this fixes your problem!