Query intermittently fails with "The multi-part identifier could not be bound"
If it's just one row, how about:

UPDATE LocalServer.DB.dbo.table 
SET [ChangeStatus] = 
(
  SELECT [ChangeStatus] 
  FROM RemoteServer.DB.dbo.table
) 
WHERE LocationID = '1';


Now you've eliminated the join and any aliases that have to be bound. Also why are you referencing both with 4-part names? If the local server is really the same instance, why not reference the local as DB.dbo.table instead of LocalServer.DB.dbo.table? If you take out the four-part name on the outer table, you can also do this for multi-row updates. It's not as pretty to do the aliasing this way, though:

UPDATE DB.dbo.table 
SET [ChangeStatus] = 
(
  SELECT [ChangeStatus] 
  FROM RemoteServer.DB.dbo.table
  WHERE key_col = DB.dbo.table.key_col
) 
WHERE LocationID = '1';


And as we discussed offline, if it's multiple rows and multiple columns, you should use something like this:

UPDATE t
SET [ChangeStatus] = r.[ChangeStatus],
    [OtherColumn]  = r.[OtherColumn]
FROM DB.dbo.table AS t
INNER JOIN RemoteServer.DB.dbo.table AS r
  ON t.key_col = r.key_col
WHERE t.LocationID = '1';


I believe that proper aliasing and eliminating the 4-part name should cause less work for the relevant parts of the execution process.