onServiceConnected() not called

After some more research, I discovered this is a known issue in Android.

The second activity I was talking about was an activity which is used as content within a TabActivity.

The way to fix this was to call bindService(...) on the application context, instead of on the activity context using getApplicationContext().bindService(...)

You need to add:

<service android:name="package.path.to.your.service.class" android:enabled="true"></service>

in the Android manifest file.