Verifique se você está editando /etc/php5/cgi/php.ini
e depois de editá-lo, reinicie o php-cgi. O comando para isso deve ser sudo /etc/init.d/php-fastcgi restart
Editar:
Para aumentar o limite de tempo, você precisará encontrar max_execution_time
em seu php.ini. O valor padrão é de 30 segundos. Isso é necessário se o PHP estiver sendo executado no modo de segurança.
Para desativar o modo de segurança, procure safe_mode
no php.ini e defina-o como desativado.
Veja Página de configuração em tempo de execução do PHP para mais informações sobre isso.