Sounds like you're using a self-signed (or otherwise untrusted) certificate on the webserver. You'll either need to install the CA certificate locally on the client and trust it, or switch the webserver to use a "real" certificate issued by a commercial CA that's trusted "out of the box". The former is fine for development, but if you're going to have lots of clients, it'll be a real pain to do that for everyone.
The easiest way to install your CA certificate for the current user is to navigate to your target URL in Internet Explorer (must be IE, not Firefox- FF has its own cert store), ignore any cert warnings it gives you. Click the "lock" near the address bar (assuming IE7 or 8), hit "View Certificates", then go to the "Certification Path" tab. If there's more than one certificate listed in the chain, double-click the topmost one- if not, just go back to the "General" tab (you're already on the root cert in that case). Click "Install Certificate" and click through the import wizard. Now try your webservice client- it shouldn't fail for server security (unless there's something else going on). If it still doesn't work, try installing Fiddler and watching the SSL negotiation- you can see why it might fail (invalid certificate dates, etc). You can tweak the generated VBA client sometimes to get past these issues, but again, it's best to just use a real and valid cert on the server if you're doing this for a production app.