If you continue down the road of trying to make your service interact with the user's desktop directly, you'll lose: even under the best of circumstances (i.e. "before Vista"), this is extremely tricky.
Windows internally manages several window stations, each with their own desktop. The window station assigned to services running under a given account is completely different from the window station of the logged-on interactive user. Cross-window station access has always been frowned upon, as it's a security risk, but whereas previous Windows versions allowed some exceptions, these have been mostly eliminated in Vista and later operating systems.
The most likely reason your service is hanging on startup, is because it's trying to interact with a nonexistent desktop (or assumes Explorer is running inside the system user session, which also isn't the case), or waiting for input from an invisible desktop.
The only reliable fix for these issues is to eliminate all UI code from your service, and move it to a separate executable that runs inside the interactive user session (the executable can be started using the global Startup group, for example).
Communication between your UI code and your service can be implemented using any RPC mechanism: Named Pipes work particularly well for this purpose. If your communications needs are minimal, using application-defined Service Control Manager commands might also do the trick.
It will take some effort to achieve this separation between UI and service code: however, it's the only way to make things work reliably, and will serve you well in the future.
ADDENDUM, April 2010: Since this question remains pretty popular, here's a way to fix another common scenario that causes "service did not respond..." errors, involving .NET services that don't attempt any funny stuff like interacting with the desktop, but do use Authenticode signed assemblies: disable the verification of the Authenticode signature at load time in order to create Publisher evidence, by adding the following elements to your .exe.config file:
<configuration>
<runtime>
<generatePublisherEvidence enabled="false"/>
</runtime>
</configuration>
Publisher evidence is a little-used Code Access Security (CAS) feature: only in the unlikely event that your service actually relies on the PublisherMembershipCondition will disabling it cause issues. In all other cases, it will make the permanent or intermittent startup failures go away, by no longer requiring the runtime to do expensive certificate checks (including revocation list lookups).