El problema puede ser que el servicio se inicie antes de que el usuario inicie la sesión, por lo tanto todavía no hay ni escritorio, ni barra de tareas, ni nada. Si tu intentas colocar el icono nada mas iniciar el servicio, fallara, tienes que esperar a que se cree una barra de tareas.
De todas formas, lo correcto seria crear un segundo programa, este se encargaría de interactuar con el usuario, mostrar el icono, etc ... y se comunicaría con el servicio por medio de códigos de control, tuberías, sockects, etc ... como mas te guste. Este programa se ejecutaría dentro de la cuenta del propio usuario, al iniciar la sesión por ejemplo, por lo que no habría problemas para mostrar el icono. Solo es una sugerencia
