So here's what the problem was. The app uses GPS, and it had to keep running even when the player opens another app. This means putting all GPS-related code in a background service. Even when the app isn't in the foreground, it keeps running. The real issue was communicating between the service and the app. There are several ways to do this. One is creating a bound service, and then you can access the background service like you would any other object. Doesn't sound too difficult, does it?
The problem arose when I searched for a way to stop the service. The game has an exit button. It doesn't really exit the app (this is frowned upon bigtime in Android), but rather it stops the background service and goes back to the start screen. The problem with bound services is that Android activities are bound to it, and as long as there are any bounds, you can't stop it. It keeps track of the number of bounds and stops automatically when this is zero. And that's what gave me such a headache, because at some times, I just couldn't stop the service!
So I decided to try something else. I started the service without binding it to the activity. This means you can't access it as an object, but instead you have to send messages between the activity and the service. This is a little bit more work, but you can always stop the service no matter what.
This was the first time I used services. It's a complicated subject, but I learned a lot in the process. Now I can move on with all the rest.