I got to the bottom of it, it was the 30secs limit of max_execution_time which was causing the problem.
I spoke to my hosting provider and they replied as follows (which was to be expected)...
"We regret to inform you that we cannot change the default PHP settings on our servers. If we increase the 'max_execution_time' or 'upload_max_filesize' it will effect the performance of the server <server IP> very badly. It will increase the load on the server causing downtime for many of the sites."
But I still want to get my larger images on the site so I was wondering if the following would work...
...if I create a folder on the website called 'store' and then uploaded the images via FTP so when I add files to 4images I use the URL section instead of the file upload and then just put URL of the file - http://<mysite>/store/<filename.jpg>
Will this work?