A ver compañero, varias cosas:
1º Veo que tienes vodafone, la ROM que lleva el teléfono es de operador? Si es así, salvo que le tengas un especial cariño a Vodafone, yo de tí pensaría en sustituirla por una libre. Las de operador llevan mucha basura que hacen que el GPS funcione mal, entre otras cosas. Sorprendentemente el GPS en un teléfono como el SGS2 no está a la altura del resto del teléfono...
2º Instálate algún programa que te baje el efemérides (creo que se llama así), que es un archivo con las coordenadas de los satélites, y que hay que descargarlo periódicamente para que así el GPS vaya a tiro fijo a por los satélites. Así se mejoran considerablemente los tiempos de conexión. Hay muchos en el market: GPS Status, GPS Aids, GPS Test, GPS Fix, GPS Essentials,.... A mí me va mejor con el GPS Status.
3º Si así no mejora la cosa, tendrás que trastear un poco (eres root?): Mírate la información:
http://www.htcmania.com/showthread.php?t=226413
http://www.return222.com/2011/07/meg...ta-y-todo.html
Haz lo que te digo y ya nos cuentas. Suerte