Puedes usar explain con tus consultas para ver si algunas tardan demasiado.
http://dev.mysql.com/doc/refman/5.0/en/explain.html
Otra cosa que hice alguna vez fue tomar el momento en que inicia ejecución la pagina con time() y tomarlo al final, a veces en puntos intermedios tambien, ir concatenando valores en una variable (usando date() para que sea legible) y luego imprimirla al final de la pagina.
Ese tipo de cosas te puede dar una idea si lo que tarda es la ejecución de tu script o es otra cosa.