Hi,
We are having the same problem:
Fatal error: Maximum execution time of 30 seconds exceeded in ***/public_html/wp-includes/formatting.php on line 82
Our menu system has about 50 items in it, and upon speaking with our hosting company they raised the execution time to 60 seconds and it solved the problem.
However, our hosting company pointed out that if something takes that long to execute on a new server with a low load, then there is a deeper problem.
What is the best way of letting the WordPress guys knows about this?
Thanks