Hi Dawid
Yes, all affected users have been imported from our AD and assigned to the site. I have tried manually unassigning the site, then re-assign to see if this fixes the problem for a single user but it did not work.
[edit]
I've ended up deleting the role they were using by default and have cloned an existing editor role and culled it's permissions to a point of failure. May have been a module access issue with the original role.