Can't activate Email Service

After speaking to Salesforce support I have resolved the issue. Rather than delete the post i will answer it incase anyone has similar issues...

The support consultant literally took a copy of my class, deleted it from the system and reinstated it again. After doing this the class became compatible with the Email Service despite no code changing.

I recommend following the above steps before racking your brains over it as I did. It is obviously just a Salesforce bug...

I faced the same issue with Email Services (with a bonus of Sandbox vs Production problem).

I created a class in the sandbox that implemented the Messaging.InboundEmailHandler interface which worked fine in the sandbox but I got the same error in production, after reading the solution support gave to David I tried something that shouldn't work but it did.

I fixed the error (or find a workaround for the bug) by compiling the class in production from the IDE (I'm using MavensMate) and then I was able to create the Email Service without any problem.

Note: Just in case you can't wait for support to get back to you.