"Visual Web Developer does not support creating Web sites on a SharePoint Web server."
Arrgh.. so annoying. Luckily there's an easy workaround:
First, create a new web application in your webroot folder (probably c:\Inetpub\wwwroot) by creating a folder with explorer, and then application-izing it using the IIS Administration snap-in.
Then, go back to Visual Studio and re-try to create the web service (File->New Web Site) using the name from the folder you just created.