This is an important feature of the current versions, see e.g. http://www.odata.org/documentation/operations#ReplacingLinksbetweenEntries.
Also if we treat <entity>/$links/<navigationproperty> as a resource, it's strange that this kind of resource doesn't support PUT.