The good news is that this is a simple repair. The forks are disassembled, the damping rod is removed from the lower santion, the seal removed, and the upper and lower sections are split. There is an inner and outer bushing and my guess is that they are binding. If the shop had properly pumped the forks when they changed the oil they would have caught this. My guess is that they never bothered to remove the forks from the bike when "servicing" them and replacing the leaky seals.
The other good news...you took the time to do the "hard" work that the shop didn't want to do. And now you know, there's nothing hard about it.