I've just spent a while finding this out, so I thought I'd post it here. Even if the user has all the needed access rights to a node, if the body of the node was created using an input format that they don't have access to use then they can't get access to it.

If you find that a user randomly can't access a node then have a look at the input formats, it might be set to something they can't use.

You might only notice this if they can't see the tabs on a node page or can't view an edit link in a view.