So you're seeing the scary looking error message at the top of your Salesforce Email Services page. Not to worry! For some reason (we're not sure why), Salesforce simply displays a big error-looking message in a yellow box at the top of the Email Services page (found by going to Setup > App Setup > Develop > Email Services) that has the following text in bold at the top of it:
"Before creating email services, create Apex classes that implement the Messaging.InboundEmailHandler interface."
Scary and confusing? Yes. Worrisome to our Soapbox Mailer organizations? Nope.
You can gleefully ignore this message and continue on your way.