That phrase has always struck me as particularly American, and western American. In many places people talk of "getting the locks changed" rather than "changing the locks". It's the difference between doing something to the locks rather than swapping them out for new ones. I guess that is a reflection of the general poor quality of locks used in the US: Buying a new lock is cheaper than getting a locksmith to rekey an existing lock. And when I was on the east coast I do remember seeing more locksmiths (at least their storefronts/trucks) than on the on the west.