Are you sure you have deployed the compiled classes in the right location and including the method (latest class files). Most often this is where the problem starts.
There are multiple things that you need to verify.
1. Check if you have classes (most probably) directory added as custom classpath in component hda file using component wizard.
2. Verify you have added classes directory as component classes entry in component menifest file using component wizard.
3. Verify Service Handler registration table serviceName column value matches service type value of service in service definition. Service handler serviceName column can be set as "Service" so that any service can use method defined in this service handler.
4. Verify method name in service handler java file is same as written in service definition.
if all of above are good then build your component and re-install on your system and restart.
Sometime server classpath variable is not updated with component classpath value on restart. I have observed it in past.
Hopefully you should be able to run your service after that.