I’d got the same error log like you.
After i’d read many reference, and this
http://wordpress.org/support/topic/custom-permalink-dramatically-slows-website could finally solved the problem.
Although i can’t use “fancy” permalink anymore, but i still can use %category%.
I use /%post_id%/%category%/%postname%/ for permalink, and no more slow response site also no more that error log anymore.
