Are you sure that you have the gib oriented correctly? What type of gib do you have? I have seen two types, one a wedge that is pushed in or out to achieve the proper clearance and the other the has multiple set screws push the the gib against the ways. If the first is inserted backwards, it simply won't work. The second type usually has at least one screw that engages a recess in the gib to prevent it from sliding back and forth. If the screw isn't seated in the recess, it may not be possible to loosen the gib sufficiently.
For the wedge type, a careful inspection will reveal one end having a larger gap than the other and the gib being thinner on one end than the other. The thin end of the gib should be inserted in the wider gap. For the multiple adjustment screw type, I back the screws out and insert the gib to the approximate position. Then I slowly tighten the scre until it contacts the gib and move the gib slightly back and forth until the screw loosens as it settles into the recess. Then I advance the scre another half to full turn , mnaking sure the gib still is free to move. It should now be positioned correctly and you can continue the adjustment procedure.