La tabella ha degli indici ? su che colonne ?
Che tipo di ricerche effettui ? quali sono le query che usi ?
Il risultato della query quanto è grande ? (cioè ti viene restituito un dataset da 100 righe o da 2000000)

(non ultimo, ovviamente, su che hardware gira ? perchè se mi dici che hai un pentium 2 con 64 MB di RAM )
Scusa l'ignoranza, come avrete visto di MySQL so davvero poco, e non ho ben capito gli indici sinceramente.. Ma comunque no, la tabella non dovrebbe avere indici.

Per il momento l'unica query che è provato è stata del tipo che segue:

codice:
SELECT * from geoname WHERE asciiname like '$cityname'
Il risultato sulle 2 - 3 query che son riuscito a provare è risultato 0.. Ma in linea di massima dovrebbe essere restituita una sola riga

L'hardware non è il massimo ma neanche un pentium 2 con 64 MB, ho un i7 da 2.2 Ghz e 8 Gb di ram..