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.