Hello, @alana.marks . . . that would make sense if it was his feet sticking.
Some suggestions for cleaning the feet that I have seen are in this thread.
You might want to try the tips there and let us know if it fixes his walking issues. Yes, some surfaces can be bad for their feet, so that may have been what caused it over time.
Let us know how it goes.