I am also having the same problem....

Contacted my host, hostonnet, for those who also use it and was told that shared servers, max_input_time and max_execution_time is 6000.

How long would it have to be to work?

I cant afford a dedicated server for such a small site, is there any other solutions to this?