This might happen if a process in your service takes longer than a certain amount of time to execute.
What I mean is that Windows allows a certain amount of time for a service to stop, I don't know how long that would be, but let's say, for example, that it's 60 seconds. If you have, say, a Sytem.Threading.Thread.Sleep(100000) in your service code, or if the service's System.Timers.Timer's interval is set to longer than 60 seconds, then Windows will assume that the service has failed to stop, regardless of whether it actually has or not. The easiest way to check this is to see if the service does actually stop, even after the error message.
I suggest adding an OnStop() event to your service, to kill any timers running or and threads that may be sleeping, this should solve the problem.