Steve Mushkat
The culprit is the account you're using. I'm doing something similar in code, and when I use an admin account, when I access the SPSite.AllWebs property no problem, but when I switch to a visitor user I get the access denied exception.
The solution to this is to use impersonation inside the code - inside the code you can switch to a specific user ID to use, or there's a technique to switch to the service account ID (you can probably find this documented out there, haven't tried my SP2003 code on MOSS to know if it works yet). If you can control the account used by the web service give that account site admin access. Remember if you have to store a credential to use, even in code, best to encrypt it!!!
For me, I'm trying to show the user the list of sites they have permissions to see, so I can't really use impersonation - otherwise the user will see all sites regardless of their site access. So instead I'll need to add in some code that checks the user's site permissions then decides whether or not to show the site.