Posting this as it can help some one with same issue
Error message: navigating to Service > Service Calendar will show error
The requested record was not found or you do not have sufficient permissions to view it
Cause: This morning i have received a request to resolve duplication issue and i had to delete a user from CRM via SQL, had to delete entries from below tables
teammembership
usersettingsbase
queuemembership
systemuserbase
Usually any Active directory user messup should be resolved by reimporting organisation which does remap users, but it did not work either
I had to open service activity and tried to save and got same error as above, but detailed error log was helpful
Pointer record exists but referenced record of type 8 not found: <<<guid>>>
I had to delete the entry from resource group too.
hope this will help someone and save their time.
*This post is locked for comments