Please refer to this example
http://jsfiddle.net/SE5jc/. It seems that there are no problems with the 'fitColumns' method.
Click the 'HideF5' link to hide the column 'f5', the columns re-fit fine.
Click the 'HideF3' link to hide the column 'f3', the columns can't re-fit because the 'f3' is a frozen column. Click the 'ReFit' link and you will see re-fit works fine.
With the 'fitColumns' property set to true, the columns will be stretched to fit the remain column width. Thus the horizontal scroll bar will disappear. The user does not need to define the 'frozenColumns' again.