yes, that sounds probable. cell reselect hysteresis, or maybe cell reselect offset (or both) are set at a too high value.
but in this case, when finally camping on the new cell, in the new LAC, (which means for the MS : “need to send a new LU message”) the location update shouldn’t suffer from a problem : the new cell should have a much better level than the previous one. So the LU should be fine ? It is worth checking it out anyway.
Also, check SDCCH congestion in the cell, check the LU/call ratio, and check the radio conditions.