Check the application pool that the web service  is running under, it
should match the application pool where sharepoint is installed

Let me remind you my issue is with windows  service using sps/wss
object model, it has no problem in accessing webservice deployed on
any server.
Now coming to the point widnows service  communicates well with a
webservice, but now i want my windows service to talk to web service
only on need to talk basis  for which i have to enforce some rules for
accessing webservice, and those rules are based on SPS/wss object
model. I have also tried to impersonate the current accunt but it did
not work.
note: My Environment is small server farm, and m using service from
administrator account on front  end server which is also admin on db
server.
but when ever i try to use object  model in windows service i get the
following exception,

Service cannot be started. Microsoft.SharePoint.SPException: Cannot
connect to the configuration database. --->
System.Runtime.InteropServices.COMException (0x81070555): Cannot
connect to the configuration database.
at Microsoft.SharePoint.Library.SPRequestInternalClass.OpenSite
(String bstrUrl, Boolean bGetUrlOnly, String& pbstrServerRelativeUrl,
Guid& pgSiteId, Int32& pOwnerID, Int32& pSecondaryContactID,
DateTime& pdtLastContentChange, DateTime& pdtLastSecurityChange)
at Microsoft.SharePoint.Library.a.a(String A_0, Boolean A_1,
String& A_2, Guid& A_3, Int32& A_4, Int32& A_5, DateTime& A_6,
DateTime& A_7)
--- End of inner exception stack trace ---
at Microsoft.SharePoint.Library.a.a(String A_0, Boolean A_1,
String& A_2, Guid& A_3, Int32& A_4, Int32& A_5, DateTime& A_6,
DateTime& A_7)
at Microsoft.SharePoint.SPSite.get_ServerRelativeUrl()
at Microsoft.SharePoint.SPSite.get_Url()
at MyNewService.Service1.OnStart(String[] args)
at System.ServiceProcess.ServiceBase.ServiceQueuedMainCallback
(Object state)

I am also doing Same Windows service  and getting acess denied.

But My code  is little bit different, I have remove the hardcoding of Website
name.

Following is Code( in c#) i have used, If it help u and solve ur problem,
plz forward it to me also since i am also facing problem.

----------------------------------------------------------------------------
----------------------------------------------------------------------------
---------------------
SPGlobalAdmin GlobalAdmin = new SPGlobalAdmin();
SPWeb MyWeb;
foreach(SPVirtualServer vServer in GlobalAdmin.VirtualServers)
{
if(vServer.State == SPVirtualServerState.Ready)
{
SPSite SiteCollection = vServer.Sites[0];
MyWeb = SiteCollection.RootWeb;
}
}
SPUser MyUser = MyWeb.AllUsers.GetbyId(1);
MailMessage Msg = new MailMessage();
Msg.To = MyUser.Email;
Msg.From = "Chandan@...";
Msg.Body = "This is Test Mail from Windows Services";
Msg.Subject = "Test Mail";
SmtpMail.SmtpServer = 192.168.2.105;

I have also tried ur code  with current user as administrator on every
level. but still its not working, i have tried this code by even
impersonating it as administrator at runtime and also with out
impersonation, but it has same old poor results that
"
Unable to connect to the database SPS01_Config_db on PORTALSERVER.
Check the database connection information and make sure that the
database server is running.
"

here is the detail exception ,
Service cannot be started. Microsoft.SharePoint.SPException: Cannot
complete this action.

Please try again. ---> System.Runtime.InteropServices.COMException
(0x80004005): Cannot complete this action.

Please try again.
at
Microsoft.SharePoint.Library.SPRequestInternalClass.GetSiteCollection
(Int32 lIISInstanceID, UInt32& pdwColCount, UInt32& pdwRowCount,
Object& pvarDataSet)
at Microsoft.SharePoint.Library.a.a(Int32 A_0, UInt32& A_1,
UInt32& A_2, Object& A_3)
--- End of inner exception stack trace ---
at Microsoft.SharePoint.Library.a.a(Int32 A_0, UInt32& A_1,
UInt32& A_2, Object& A_3)
at Microsoft.SharePoint.Administration.SPSiteCollection.b()
at Microsoft.SharePoint.Administration.SPSiteCollection.get_Item
(Int32 index)
at MyNewService.Service1.OnStart(String[] args)
at System.ServiceProcess.ServiceBase.ServiceQueuedMainCallback
(Object state)