I probably figured out what happened. I have a limit on the number of simultaneously open MySQL connections. I keep track of them using a semaphore so that if the limit is exceeded, the next thread would wait for an available connection. The only slight problem is that both this waiting and the releasing of connections into the pool are done from synchronized methods. I can't believe this problem didn't show itself until now. I also can't believe how stupid I am sometimes.
Setting the connection limit to 3 and running this load testing thing makes it hang every time. YIKES.