Services do not run in a different thread. Unless you are using the Threading library, your code always run in the main thread (libraries code can run in other threads though).
See the documentation for StartService:
Basic4android Search: startservice
It says that a Msgbox cannot be shown after this call and before the service has started.
I will explain it. When you call StartService a message is sent to the message queue. Once this message is processed the service starts. If the service is not started after 20 seconds, Android will force close your application. Therefore it is not possible to show a Msgbox at this time. You can change the order of the statements and first show the Msgbox and then call StartService.