To help track down where the actual slowdown is coming from, try adding &debug=1 to the end of a couple of your urls.

Like:

http://www.dancescape.com//ubbthreads/ubbthreads.php?Cat=&debug=1

This will give you a breakdown of each query made and the time it takes to execute. This will help track if it's a specific query, the mysql server itself or general server speed.