I'll need steps to reproduce the problem in order to troubleshoot the cause.
when they get the Product Cannot be found message, What product link are they clicking?
And what is the full address in the address bar?
i cannot troubleshoot a problem without being able to reproduce it.