If you're getting a 403, that most likely means that the server is expecting some kind of credentials, and if you get a cert popup in your browser that most likely means that those credentials are a client certificate. (A 403 could also mean that the server doesn't like you for some other reason, like IP address, but given the circumstances this seems less likely.)
Assuming the service wants a client certificate, you would need to explicitly associate the client certificate with the call either through code or in your configuration file. (How you go about this would depend on whether you're using WCF or classic Web Reference web services.)
It sounds like the certificate you were given by the provider might be the client certificate the service is looking for. If so, it would need to go into the "My" store for LocalMachine rather than Trusted Roots (because a client certificate isn't going to be a root certificate), and you would need to configure your code to use it in the request.