Problem comes from the fact that in Windows (and specially since versions 6.x) services run in a completely isolated session and desktop, without any chance of user interaction, which is by design and discouraged to do so, for security reasons. The program you're launching actually does starts, but it does so in that hidden desktop (same for notepad) where no users can ever see it.
The quick and dirty workaround is to mark the service as interactive in the control panel, and start the interactive services detection service. When doing so, when your service runs the program, a window will flash in the taskbar, telling there is a message from a service, so that you can switch to that parallel desktop and actually see it. That's simply very inconvenient to the user and widely considered a BAD PRACTICE.
The real solution is to make the program a regular application and not a service, and run it though some autostart location in Windows for every user. It does not need to have visible UI, but run in the same context as you do. Or to leave the service, but also put some application in user space that communicates with the service just for the sake of running the second program. In any case, the general rule is to never have any kind of user interaction from a service process.
Here is an article that explains the problems and some workarounds http://blogs.technet.com/b/askperf/archive/2007/04/27/application-compatibility-session-0-isolation.aspx