I've come accross this problem before ages ago, and found that the service didnt start because other relevant services hadnt started yet. 1 way round it is to have a script to run on startup to start the service, and then put a decent size pause in the script to allow the other services to start first. I also think there is a way to change the priority/way services load up, but I cant remember how you do that or if its still possible on the 2003 server.
If its another problem, then you will need to post any event viewer details and other relevant info you have which might give us all some more ideas :)