So I assume that the user is also not able to save links to a record?
But be aware that the record link table is not connected to a specific company. So the user needs the access to record link table without a specified company.
I ran into the same issue (NAV 2013R2). I went ahead and assigned the the basic role which has the Record Links table to user with no specified company and we are still getting the same error.
As of last week, all users could add notes and links and the basic role was company specific. We have not made any changes to NAV since last week and just don’t know what changed that we cannot add notes.