Wow, this was almost maddening ... I tried to deploy a webservice to a windows 2003 server and kept getting a FileNotFound exception on some wierd files in the c:\windows\temp directory. Read on to see the fix
After reading this kbase article, I realized that the asp.net worker process needs read and write permissions to the %windir%/temp directory as this is where webservices creates "serialization proxies".
Simply give the asp.net worker process read/write access to this directory and you should be golden