A couple of thoughts come to mind:

1) Airtable recently launched 2-way sync to allow editing between synced tables from both sides of the sync. In order to populate a linked record field that is linked to a synced table coming into this base, you will need editing capabilities introduced by this new 2-way sync functionality (as a linked record field populates in both places). My guess is that you need to enable your Staff source sync to "allow edits from other bases" for the permissions issue to resolve.

2) I haven't tested this theory with datasets also being new, but I wonder if edits can not be 2-way to a synced dataset as this could lead to verification confusion when your dataset owner/admin has verified a dataset and then your end user can edit it.

oooh ok, interesting!

starting with #2, it seems you are right about 2 way sync and data sets:

RE #1, i don't think it's a two-way sync thing, since i've been using this linked record automation with other synced tables/data sets (like my master schedule, and a base with curriculum info).

but, playing with this led me down another path & unlocked another weird thing.

basically, i reversed it: 

in my synced Staff table from the data set, I copied the name of the Staff record into the "Link to Classes" field that was created when I tried to link them from the other side, and it let me! 

so i was like, "cool, i'll just automate it from the other direction"

but then i looked at my Classes table and.... lol, not what i meant to do. it's linked, but to an entirely new record that it named itself?

more symptoms identified, but still no cure!

re: datasets, good to know!

When you populate a linked record field with a value that does not correspond to any existing record in the linked table, Airtable will create a new record in the linked table and assign this value to the primary field.

UPDATE: 

I solved my own problem. It was indeed a newbie error with an easy fix:

There was an extra space between names in my "Staff" table (which is actually syncing from a Salesforce report, so I didn't even check the entry of the names). Lesson learned: Make sure your records are exact matches, lol.

Hi @rking 
It seems I have a similar problem, but your solution does not work with me.

In my case, I have 2 bases that are 2-way synced. I am the owner of both bases.

Base A is the master, Base B is the receiving base
In both bases, I have two tables : People and Meetings
In Base A, People are linked to Meetings.
In Base B, in the Meetings table, linked People appear as text strings (Column A). So far, nothing weird.
In order to re-link both tables in Base B, I have re-created a linked column (Column .
I have created an automation that copies Column A and pastes in Column B. The automation runs smoothly 95% of the time but sometimes, it fails "due to insufficient permissions".

I cannot figure out any reaason why it would fail. Any lead ?

Thank you

The issue in my case was that the text strings did not match exactly!

When the automation tried to link a record in Table 1 to one that "doesn't exist" in the Table 2 (in my case, it was the double spaces between first & last names in Table 2 vs the single space in Table 1), Airtable tried to create a new record in Table B so that there was something to link to. Since your Table B is synced, you might not have permission to create a new record in Table B. This was the source of the "insufficient permissions" in my case!

I was only working with a one-way sync from Salesforce -- it's possible that your error is coming from a different issue since you have two-way sync on 😞 

Good luck!!

I was having a similar issue. Staff at my org fill out reimbursement request forms, and one fot he staff members had not capitalized their first or last name when they made their account. When they submit the form, I have a formula set up that copies the submitters name and pastes it in a linked record field that links to a staff directory table so I can look up other data associated with that staff member for succeeding automation (in this case, their Slack ID). Since the staff member's name was capitalized in the directory, the formula failed due to insufficient permissions since it was trying to copy a name into a linked record field where there was not record in the linked table that EXACTLY matched the name of the staff. I fixed the staffs name in their account and now it works fine. 

It's such a stupidly easy solution to a problem that gave me such a headache, hahaha. Glad you figured it out!

Not sure if it's possible for you, but when I have coworkers fill out forms, I usually make them pick names/important items via a linked record field instead of typing into a text field. (So in this example, they'd pick their name from a separate Staff table.) That way there's no potential misspellings, and sometimes it cuts down on need for automations. It also means my staff table has 1 million hidden linked record columns for different uses, but c'est la vie.