When the seat is off the car, the rails can be easily misaligned by rough handling as the metal strip which spaces them is so flimsy. This can contribute to the adjustment being stiff.
More likely, if the floor has been replaced, is that the runners on the floor have been incorrectly made....either spaced badly or the lip being unevenly sized along its length or simply being too wide. This makes it bind within the runner under the seat. I've had to grind the floor runners down to get a better sliding fit. Grease is still needed but is not the major part of the problem.