We had a similar instance, where a linked server that once functioned for certain users stopped functioning. Our solution was actually to increase the permissions on the Windows server for the Windows user under which the (local) server instance was running as a service. Not sure if it was a Windows OS update, or something else that caused the issue, but that solved it.