"All circuits are busy" message received randomly when dialing out from Trixbox 2.8.

We have a server running Trixbox 2.8 / Asterisk 1.6 and when we dial out, we will randomly get a message stating "All circuits are busy now."  This seems to happen randomly and if we redial the same number after receiving this message, the call almost always goes through without a problem.

We have two separate trunks set up using two different methods as posted below.  Both of these trunks have these random failures.  The service provider says they usually see a 503 message on their end, or nothing at all.  I get this message from the Asterisk server: == Everyone is busy/congested at this time (1:0/1/0)

The provider did some more digging and found that the sip headers are sometimes being passed incorrectly.  
Example of incorrect header being sent:
From: <sip:x.x.x.x:5060>;tag=31d8e646+1+0+71f506db
To: <sip:x.x.x.x:5060>;tag=as7e7c519b
Example of correct header being sent:
From: <sip:"CallerID”5555551000@x.x.x.x:5060>;tag=31d8e646+1+0+71f506db
To: <sip:x.x.x.x:5060>;tag=as7e7c519b

The test trunks that we have set up are below as well:

[TEST_TRUNK_1]
disallow=all
allow=ulaw
canreinvite=no
dtmfmode=auto
context=from-trunk
fromdomain=x.x.x.x
host=x.x.x.x
nat=never
insecure=invite
outboundproxy=x.x.x.x
qualify=no
srvlookup=no
type=peer
secret=secretive
username=##########
defaultexpirey=3600

[TEST_TRUNK_2]
host=x.x.x.x
type=peer
dtmfmode=auto

[TEST_TRUNK_2_USER]
host=x.x.x.x
type=peer
dtmfmode=auto

Has anyone else had these problems before?  Is there something I need to change on our system?