1. Check what the service account of the reporting service is. Is it a domain account or network service?
2. Run this query in SSMS and note down the details: select dbo.fn_FindUserGuid(),SUSER_NAME()
3. Run this query in SSMS: select SystemUserId,FullName from SystemUser where SystemUserId in (select dbo.fn_FindUserGuid())). Does this produce any rows?
4. Open new query tab and run "execute as user = 'AD ACCOUNT FROM STEP 1'
5. Run query in step 3 again
6. Now run the query that powers the report. Check if it gives any permission errors.
7. Run this query to rollback the user impersonation on the current SSMS tab: revert
This should give you some direction on what the underlying error is.