How are you connecting to your provider? Does your pix firewalls direct connect to their switch?
It sounds like a failover issue, where both pix units think that they are acive, or none one does.
Usually you can tell by looking at one of the LEDs at each pix (I think it is the one labeled ACT).
If your pix connects direct to the provider switch and that switch is a layer 3 device too, ask if rapid span-tree is not enabled on the pix ports. Cisco recommends that the portfast (a cisco feature of rapid spantree before it became an IETF satndard)feature be configured for pix conns on cat switches.
I am thinking that span tree waiting 30-90 seconds to allow the pix ports to forward traffic may be the cause of the invalid active/standby state or make the problem worse.
Let me know what you find.