Its not a "hosting problem", im sure of it. Of course, if you blog start using something like 50% or more of the CPU cycles in a shared host, you will be banished for sure, but im having the same problem after updating to 2.5.
I ALWAYS tracked my CPU and SQL usage, and after updating to 2.5, some pages started to use more than 2000 queries to be shown!
using the debug-queries plugin, here is what I got from the logs:
4.29153442383E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
4.19616699219E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
4.6968460083E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
4.19616699219E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
4.19616699219E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
4.41074371338E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
4.29153442383E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
4.2200088501E-05 SELECT post_parent FROM wp_posts WHERE ID= '286' LIMIT 1
This line got repeated in my logs like 2000~3000 times PER PAGE, so im pretty sure its a wordpress bug, since i disabled all my plugins and the problem still occurs