I was having problems getting my labels to wrap - you solved the other half of the problem. I didn't realize I needed a percent column - 100% worked great with the other columns set to "autosize".
The two things I would check in addition to "AutoSize=true" is that the labels have a FlatStyle of Standard and that Anchor is "Top, Left, Right". The right anchor is looked at by the TableLayoutPanel to determine where it should wrap, AFAIK.
Hope that helps!