Dial the access code to the trunk you're trying to get out of, then the local number. Does the call go through, or do you get a recording from the telco?
Try other trunks (i.e., copper vs PRI, different telco, etc...) and see what results you get. Go into LD 80 and do an enhanced trace if you have to in order to see what you're sending to the telco.
My guess is it's a telco and/or LD carrier issue. Once in a while I'll get an oddball where outbound calls over Paetec to 212-555-2345 won't go through - but 212-555-3456 will. Or calls to the same number, dialed the same way over Verizon or my cell phone will go through.
If you were in an overlay area code situation (where you have two area codes now), you would be very well aware of it as ALL of your local calling would be affected.