A guess, you can check out: I remember me getting something similar when I was pointing to wrong .NET Framework in IIS.
Example, if you had this on Framework 2.0, and IIS right now is pointing to V1.1
Check it and see.
BTW, deploying webservice is same as deploying a web app:
1. In IIS7:
Deploying ASP.NET Websites on IIS 7.0 [
^]
2. In IIS6:
Deployment of a Website on IIS[
^]