If a user cannot access a public report, the most likely reason is that the report and the user exist in separate organizations.
Reports are local to the organization where it was created, so the user accessing the report must also be part of the organization where the report lives.