Class of restriction of the trunks would be first suspect, the trunk COR needs to be allowed to make the external call.
Also, depending on the type of trunk and carrier you might need to surpress the caller ID pass through.
You can always view the EDT (PRI/T1) or SIP trace and see why the call is failing.