I have encountered weird web service 404 error after I installed and configured the March CTP of VSeWSS 1.3. I call it weird, because I was expecting access denied error, but not the dreaded "File Not Found" billboard on my way to use the latest version of VSeWSS. :)
Some people have the same problem, too.
Anyway, given the fact that I was setting up the development environment on a fresh installation of Windows 2008 Web Server I figured out that the problem is caused by the fact that IIS does not know how to handle the request addressed to the service. So here is the solution:
Win+R > cmd cd "%SystemRoot%\Microsoft.Net\Framework\v3.0\Windows Communication Foundation\" ServiceModelReg.exe -i