If you try to catch last error code what do you get ?
Also based on issue I also got to make it running, Since Vista and UAC it become incredibly more complex, like crazy, (consider switching to Linux, no joke!) to use CreateProcess.
There is no longer any kind of default that can help.
Specially if the process itself that you start need special access.
It may happens that running Notepad.exe is more complex than your targeted process. So no longer the obvious choice for a "quick try"
Also you need to use CREATE_BREAKAWAY_FROM_JOB flag during creation (just to help debugging it)
and create a manifest for UAC management
see
http://stackoverflow.com/questions/89588/assignprocesstojobobject-fails-with-access-denied-error-when-running-under-the[
^]
No idea about the "service" case.
Good luck.