10秒を超える長時間の操作で受信時にサービスを開始するというAndroidチュートリアルを分析しましたが、サービスはメインスレッドから実行されていませんか?
http://developer.android.com/guide/practices/responseness.html#avoiding
サービス(http://developer.android.com/reference/android/app/Service.html)
また、長時間の操作は行わないでください。それではどちらがより適切ですか?