Olá,
Tente fazer desta forma.
Adicione a onStartCommand ao seu Service:
@Override
public int onStartCommand(Intent intent, int flags, int startId) {
}
Dentro desse método defina a flag que será retornada:
return (super.onStartCommand(intent, START_REDELIVER_INTENT, startId));
Desta maneira, se o android finalizar o service seu service será reiniciado automaticamente.
START_REDELIVER_INTENT
Se o sistema eliminar o serviço após o retorno de onStartCommand(), recrie o serviço e chame onStartCommand() com a última intenção que foi entregue ao serviço. Quaisquer intenções pendentes são entregues, por sua vez. Isto é adequado para serviços que estejam realizando um trabalho ativamente que deva ser retomado imediatamente, como o download de um arquivo.
OBS: Voce tem que startar o seu envio de localização dentro do metodo onStartCommand.
Existem outros tipos de flags para serem utilizadas como START_NOT_STICKY, START_STICKY, START_REDELIVER_INTENT.
Veja mais em: http://developer.android.com/intl/pt-br/guide/components/services.html