One thing I would try is to identify where the problem is truly.
If you have a PRI and it is on a Cisco router, prove to yourself how the call gets sent out compared to the same area code that works. Using debug isdn q931 for PRIs or debug voice ccapi inout for T1 CAS, see how the call gets sent to Telco.
If your call does gets sent to telco as 12255551212 to the parish, then I believe the problem may be with telco. Compare it to the number that works, for example, call 12255551313, and see how it gets sent. If it is the same, then it may be a telco issue.
What DNIS you send to telco will be depend on telco. For ATT LD PRIs, I have to send Long Distance calls without the 1 in front of the area code.
If you are sending the correct digits that telco needs to see to route the call properly, I would indeed call telco.
It sounds like there are no route filters to cause you problems, so this is one thing I would check. Hopefully this helps.