Has anyone had to solve an issue with cached permissions? I changed permissions on a role and a specific user isn't able to see the change?

Even after logging out and then logging back in?

Yes

Last time this happened to me I had given them the incorrect new permission

I have had it happen where users have had to clear their cache to get certain permission changes to take effect. Very rare tho, have only seen it like 2-3 times in 10+ years of using NS.