android services - error: service not registered

Ah, one of these days

mService.unbindService(mConnection);

is obviously nonsense, calling unbind in the wrong context. It should be

unbindService(mConnection); 

Additional mistake in the posted coding is the missing of

@Override
public boolean onUnbind(Intent intent) {
    // All clients have unbound with unbindService()

    releaseMediaPlayer();

    return false;
}

As a sidenote, since none of the other answers helped, I found that my error was using a different Context for bind and unbind. My bind was from the Application context, but my unbind was from the Activity context.

To fix the error, I made sure to use the same context for bindService() and unbindService().

Had a similar problem, but the accepted answer was not the solution for me. Luckily one of the comments gave me the answer:

onServiceDisconnected is not supposed to be raised when you unbind your service, so don't rely on it. It is supposed to inform you in case the connection between your Service and ServiceConnection is dropped.

Thanks to @Waqas I found the error: I was updating the boolean binded flag only inside onServiceConnected() and onServiceDisconnected(). Now I've added "binded=false" every time I call unbindService() and the problem has gone. That's it, don't rely on onServiceDisconnected