(disclaimer: I'm just guessing, no inside knowledge. certainly feels right though)
You're right -- it was related to the size of the units. Because they were larger they needed to find wider paths that weren't obstructed by terrain or other game units.
Did you guys have any idea what sort of an impact it would have in Asia (more specifically with the Korean players)?
PS. I'll never forgive the patch 1.13e. It removed the most amazing bug ever, that allowed to turn StarCraft upside down via specially prepared maps (think units changing weapons on demand, or terrain morphing at realtime). People were doing amazing things with it... for about two weeks that went between discovery and the beforementioned patch.
[1] - this was long time ago, I think around patch 1.11.