I had a similar problem, and the ability to access the desktop from the service wasn't the problem. It worked fine when not impersonating another user, but when trying to run the process as a different user it failed.
The first thing to do when it won't start is find out all the information you can about the problem. The first question is whether Process.Start returned true or false. Secondly, did you get any kind of exception when trying to start the process.
Before you can investigate fully it relevant to know whether Process.Start was run using UseShellExecute or not - this has to be false for impersonation, but otherwise you can choose whether to use it and it calls different Win32 functions depending on this setting.
If you're doing a process that needs to run as another user, don't bother trying to use .NET impersonation - the StartInfo username, password, domain are what you need to set. However, under IIS you've got some additional lockdown, and the only solution I found on Windows Server 2008 actually involved some Win32 calls and implementations of abstract security libraries. Many of the scenarios you can run into are outlined here: http://asprosys.blogspot.co.uk/2009/03/perils-and-pitfalls-of-launching.html
The sample code from that page shows how to call the library and add Windows Station and Desktop access to a user before starting a process as that user. This was what I needed to get Process.Start to work from IIS, having ruled out UAC, DEP and any other three letter acronym I could think of ;)