I tried adjusting the max_execution_time, but it still didn't work. The php online manual actually said that it wouldn't affect commands like "sleep", DB queries, etc. but I figured it was worth a shot.
The actual error said "Query failed", but I can see that it only happens on long queries.
Thanks,
Eyal