And the problem isn't really limited to links in the response; the same goes for computed links based on keys too.
In fact, links in responses are probably easier to update, because waiting for client software to upgrade can take a long time - but waiting for old versions to fall out of caches or at least dwindle to a small enough number is likely a much shorter wait.
Furthermore, when your clients are composing links based on keys, there's no good way for the server to tell a client that the uri has changed - the composition is in the client, and the key (presumably) hasn't changed, so the thing the server would want to update is out of conventional reach.
But with uri's there's at least a conventional solution - redirects. That's not going to be an ideal solution; but as a way of limiting transition pain it might have a place.
All in all, I think links are likely less painful to use than keys when it comes to uri routing changes. (But really, try to avoid changing uri's in the first place, because whatever you do it's likely going to be painful somewhere).
In fact, links in responses are probably easier to update, because waiting for client software to upgrade can take a long time - but waiting for old versions to fall out of caches or at least dwindle to a small enough number is likely a much shorter wait.
Furthermore, when your clients are composing links based on keys, there's no good way for the server to tell a client that the uri has changed - the composition is in the client, and the key (presumably) hasn't changed, so the thing the server would want to update is out of conventional reach.
But with uri's there's at least a conventional solution - redirects. That's not going to be an ideal solution; but as a way of limiting transition pain it might have a place.
All in all, I think links are likely less painful to use than keys when it comes to uri routing changes. (But really, try to avoid changing uri's in the first place, because whatever you do it's likely going to be painful somewhere).