Hola carreteboy:
Son muchos aspectos los que pueden hacer una consulta muy lenta y sin información de cómo es tu modelo de BD y cómo estás armando tus consultas pues es casi imposible darte una respuesta puntual, sin embargo estos son algunos puntos que deberías considerar para revisar:
1. Uso de índices
2. Evitar el uso de condiciones tipo IN o LIKE '%algo%'
3. Utilizar JOIN's en lugar de hacer uniones explícitas
4. Evitar el uso de select * y listar siempre los campos que se van a utilizar.
5. Implementar alguna estrategia de paginación de resultados.
6. Minimizar el uso de subconsultas.
7. Si las consultas son muy complejas, implementar el uso de procedimientos almacenados.
8. utilizar EXPLAIN para revisar cómo se están ejecutando tus consultas:
http://dev.mysql.com/doc/refman/5.0/es/explain.html
Hay muchos otros factores a considerar (hardware, comunicaciones, configuración de servidores, ancho de banda, etc) pero yo comenzaría por revisar los puntos anteriores.
Saludos
Leo.