Shot in the dark, I think you need an autoclass'ed context reference. But, I think you can skip the Context part entirely and just use the activity, both ideas below:
See if:
context = autoclass('android.content.Context')
#and/or possibly this helps
context = cast('android.content.Context', activity.getApplicationContext())
Or skipping context entirely and just using just Activity (because it IS a context):
...
intent.setClassName(activity, 'org.myapp.AndroidService') #this is where I'm stuck
#source file built from dist/default/src/org/myapp/AndroidService.java
activity.startService(intent)
I am working with a lot of services on my android app and I take a slightly different approach, but YMMV. In short, I treat the PythonActivity like it's a Facade to the rest of Android. So service creation methods are exposed there, but I code the actual creation work in Java and keep the interface pretty simple.
In order to make development and testing go by faster, I use a dummy activity that is Android-only to stand in while I sort out the java side. Then I just port the hook methods across to PythonActivity when I'm done. I know this makes pyjnius a less sexy, but it has some limitations (for example, it's a door in, but there's currently no "calling from" Java, not sure about Exceptions either).
Best regards,
-db-