I hope I can help someone with this info as well: I moved my service class into another package and I fixed the references. The project was perfectly fine, BUT the service class could not be found by the activity.
By watching the log in logcat I noticed the warning about the issue: the activity could not find the service class, but the funny thing was that the package was incorrect, it contained a "/" char. The compiler was looking for
com.something./service.MyService
instead of
com.something.service.MyService
I moved the service class out from the package and back in and everything worked just fine.