Tracked the problem down to a lack of memory.
I couldn’t override the memory_limit in php.ini or .htaccess.
However, I was using the direct resize module and I noticed some improvements in 1.1.1 to the resizing.
At the moment I’m stuck with 1.0.19700 for various reasons so I’ve pulled the enhancements back to that version and dumped directresize.
The good news is, speed has increased by at least a factor of 2, and memory usage has decreased dramtically as well. I would recommend not using directResize and instead use the newer versions of magento or follow the suggestions in the forums about the resize function.