I seem to remember an identical thing happening last year to a site I was working on…I updated PHP to 5.4, and then increased the memory limit, and also ran all WordPress and plugin updates and that solved it. (one of those things…)
The other thing was the client was travelling, and his internet connection varied wildy…many IP companies give decent download speeds, but minimal upload speeds.
Trying to upload a bunch of high-resolution tourist photos was causing all sorts of issues in certain countries. Teaching the client to reduce image-sizes and editing helped a lot.
Sometimes a problem can be multiple things working together to give you head-aches