Try checking the setting for
max_input_vars in your main php config ini file (if running 5.3.9 or higher), or
max_input_nesting_level (if running only up to 5.2.3).
In the past we have had some issues when testing on different servers when there are a lot of entries in the quick redirects. Since some installs of php set a default number, and the redirects and destinations are form input fields, this can max out. Usually what happens is the other items max out first (like the max_execution_time, the memory or the max_input_time) but since you have increased those, it is probably now an issue of the number of fields being submitted. There is not a whole lot of documentation out there about setting this parameter, but in our tests, setting it to 3000 worked well in almost every case.
After setting that, you usually need to restart Apache (if you have that option), or you just have to wait until the hosting provider restarts it again for something else, like an update or something. It does not usually take effect until after a restart though, so without it, you may not be able to tell if it worked for some time.
I believe (don't quote me on this) these parameters can only be set in the master ini file and not in the root or sub directory php.ini files and definitely not via php ini_set. In some cases, you may need to have your hosting provider change these if you do not have access to the main ini file. They don't always like to change them on a shared hosting plan, though, so be forewarned. In our tests, adding them to the php.ini files had no effect, it was only when we added them to the main ini file did they work.
Best of luck,