Yo pasé por lo mismo que tu... Aunque a mi me atracaron por la calle de noche dos tios. Encima, de listo, no tenia puesto el menu de bloqueo de los circulos, y mucho me arrepiento de ello, ya que de ese modo solo podrian apagarlo, pero no ver/usar ninguno de los programas que tenia dentro.
Hice lo mismo.. llamé a vodafone y pedi que restingieran las llamadas. Acto seguido, cambié las contraseñas de Gmail, foros, etc. También llame a la poli para que tuviera constancia.
Al dia siguiente puse la denuncia, con el IMEI del telefono, y la pusieron en lista negra.
Me hicieron ir a ver unas fotos y tal pero nunca más me llamaron de la poli, y el movil no volvi a verlo.
Vodafone lo unico que hizo fue romper el contrato de permanencia. No me valió ni amagos ni nada... La unica opcion que me dieron era pagar 210 y pico puntos, gastar todos los puntos y otra permanencia de 18 meses... Al final me decanté por comprar una HTC Magic por 200 euros de segundamano.es a un chaval de mi ciudad, en mano, con factura vigente durante año y medio.
Ojalá te funcione el amago o algo.. porque (al menos a mi) despues de tener un android, no vuelves a querer otro movil convencional.