Then I agree with Brogan. There must be a "Never" permission somewhere in one of that user's groups. Check the group permissions, node permissions, and user permissions if you have set any.
edit - and it is important to reproduce the problem first. You can't fix a problem that you can't reproduce. Don't trust your users.