Ensure that your "autoleveling" is actually physically leveling the bed, and not merely using software to compensate for a bed which is not level. This compensation will give you a skewed print, and your vertical rectangles will actually be non-rectangular parallelograms.

This is especially important when printing with multiple heads, as the compensation for one head will not be the same for the others.