For Authorize.net, if you're using the latest version of Zen Cart, turn on debug logging in the module and check the /cache/ folder for the logs after you try a transaction ... see what it records as the details it tried to submit for the payment ... specifically which address it submitted ... and whether the province was submitted as a province instead of a country, etc.

For Cybersource, sorry, I'm not familiar with how they work. You could try figuring out what it's submitting and what's wrong with it, perhaps by contacting their help desk to have them look at what's being rejected and why.