Remove the company of the product, leave it blank, save the product and try again. That way the product is not owned by any specific company and is visible, usable and selectable by all companies.

Besides that, the error you describe refer to "Location", like the location of the product in question is in other company different than the user belong.

This is known bug, and its old, from beginning of 7.0 I suppose they (they=OpenERP) are not able to fix it, or not interested to. I can confirm it on different modules. Specially when one user creates another and modifies his rights. The Admin is not affected. If the users are created by the Admin they are not affected. (This is what I found out)

have fun