Android Context.bindService always returns false and ServiceConnection object is never triggered

I have followed the Local Service example provided by Google, but my Context::bindService(...) always returns false and there is ServiceConnection::onServiceConnected is also never called.

I understand that Context::bindService() returns immediately, but my ServiceConnection object is never triggered.

I don't know if these apply

1. My activity is running inside a tabHost and I was wondering if that can affect service binding in any way.
2. The Service itself may have a problem, but I can call start service to the same service with the same Intent and it works as expected.

Does anyone have experience with this? Please help me out.

Thanks, P.S. I am targeting Android 1.6