Hi,

Troubleshooting steps:
1. Make sure whether the user has access to record ids of the lookup fields and/or master-detail fields in the record.
2. Check the user Profile(CRUD Permissions).
3. Profile need to have access to the record types.
4. Record's OwnerId automatically gets a shared record when the record is inserted. If the apex code tries to create the same(Share record for the owner) explicitly. This error occurs. 
 
Sample Code for this error:
 
Id usrId = UserInfo.getUserId();
Account objAccount = new Account( Name = 'Testing', OwnerId = usrId );
insert objAccount;
AccountShare objAccountShare = new AccountShare();
objAccountShare.AccountAccessLevel = 'Edit';
objAccountShare.AccountId = objAccount.Id;
objAccountShare.RowCause = 'Manual';
objAccountShare.UserOrGroupId = usrId;
objAccountShare.OpportunityAccessLevel = 'Read';
insert objAccountShare;

5. Check whether the apex code is trying to create share records to the record which the current user doesn't have access to it.
 
6. Check whether there are any hard-coded ids are miss matching the environments.
 
Note:
Even though the trigger runs in System Mode, Sharing Settings will be checked. Only CRUD and FLS will not be checked against the user.


For further suggestions check this,

https://salesforce.stackexchange.com/questions/5546/how-to-fix-insufficient-access-rights-on-cross-reference-id


Let me know if it helps you and close your query by marking it as solved so that it can help others in the future.

Thanks.