We have a windows service that runs fine on Windows 2003, but I have noticed that on 2008 it does not work the same. One of the things it does when it starts up is checks if a couple folder locations are present. For example, on a server named 'Test', I might check if \Test\ServerShare is present and if not, create it. The folder is there and it is accessible by the time I log on, but when the machine is rebooted and the service starts, it can't find it. I was going to make the service sleep for 30 seconds or so when it starts but that seems so kludgey.
Try setting the service to "Automatic (Delayed Start)" instead of "Automatic". It's probably starting before the server service has finished starting.