Closing this thread. Turns out the issue was Object Caching. Too many objects combined with a too-slow filesystem by Bluehost caused the timeout issues.
Not sure why this suddenly became an issue in 0.9.5.2, but if you run into a similar problem this is probably the first thing to try.