I had a similar problem, one service in background take gps info each 2 minutes, when I run my APP with the service already in background , my APP execute again another ServiceStartAt and overlap the service in background. I don't know if this your issue?, I fix it with this in my MAIN activity, the service "THESERVICE" has inside the ServiceStartAt.
If IsPaused(THESERVICE)= True Then
StartService(THESERVICE) 'the service is not in RAM in background so time to start it.
Else
ToastMessageShow"THESERVICE is already running",True)
End If