Is it possible that your service starts before SQL Server can accept logins? When you installed the service using
SCM did you make SQL Server a dependancy?
The easiest way to test this is to manually start your service. Since the system is already far enough into the startup sequence to allow user logins, you know that SQL Server will already be started. If your service starts then, you need to work on your dependancy list.
-PatP