This was because on the first refresh it has to process all the data before it can incrementally refresh the dataset.
As per the documentation the default timeout for a SQL Server database is set to 10 minutes, and when I am processing a lot of data it can easily take longer than 10 minutes to return all the data.
Read on to see how you can change that if you need to.