Revisa
este código de Luis Navarro, para descargar imágenes en Android. Yo lo he usado
en esta aplicación de Android (sin ser un servicio) y funciona perfectamente.
A ver si con esto consigues realizar la descarga.
Revisa
también este mensaje a ver si te sirve esa solución.