this is what I would do:
-run the report in a different company or different environment (i.e. in sandbox), or even in a Cronus company in their environment to see if the issue is with the company/data or something else
-run the report with filters (specific item, range of items, specific locations, etc.) to try to find if its still slow or a specific record is making it slow
-check the no. of unposted sales/purchase orders, do they have a lot sitting there the report has to go through
-if its happening during the work day, are they posting a lot of transactions at the same time the report is run