Have you checked the value filled in for 'metadata status', 'active status' and 'usage rights'?
Attributes can be marked as 'Required for completeness'. If an asset has incomplete attribute data, ie. an attribute marked as 'Required for completeness' has been left blank, then the asset is considered incomplete. This means that it is not visible to users who do not have upload permission for the folder/category that the asset is in.
This can allow a workflow for uploaders, to only change the status to 'complete' once all the metadata is filled in and they are happy to release the items to the other users.
Non-admin users may also be restricted to only seeing 'internal' usage rights and 'active' active status assets.
This is configurable from the Admin area, in the Admin > Groups > Attribute Exclusions area. If you tick any of the boxes, the users in that particular group will be excluded from seeing assets with that particular value.
Note that if a user is a member of another group for which the attribute exclusion settings allow the asset to be seen, then that takes priority and the user will be able to see the asset.