When this happens to my users it's usually a project scoping problem. I'd check:
- If someone sends your user the direct URL to the story, can he see it or does he get an error?
- Assuming he can see it that way, is his project context in the project explorer the same as his teammates?
- If there are child projects, are you quite certain that the story in question is assigned to the project that your user is scoped to? If it's in a child project then make sure that he has the Show Items from Child Projects checkbox set.
Failing all those solutions you might need to open a case with CA. Hope that helps.