thanks for your response. The issue is not browser related. We have tried different browsers and machines.
Two things we have worked out:
1. It's the first refresh of the day that didn't work. The second works (no matter if manual or scheduled), so the subject of this thread is not accurate anymore.
2. I have created copies of the report and in each copy I have removed on of the SQL tables in use. One joined table seems to cause the problems. Once this has been removed from the report, it refreshes (on the first refresh of the day).
So, still no idea what the problem is really, but I found some workarounds.