Ok, there is no guarantee that the TE122 has echo cancellation or not. Fortunately On digium cards it is fairly easy to tell if it does. Open up the case, look at the card, and see if it has a small purplish/blue daughter card on the main part of the card. If it does then that is the echo cancellation.
Other then that it sounds like you may potentially have bad termination at the telco. If the DSP or terminating switch has a problem past the CSU/DSU then it would not show up in testing. The intrusive testing is an interception of the circuit before termination to test the physical line and transmission. If they are running a new pair then you will be getting a new circuit. If it works on the new circuit then it was something associated to the circuit path on the old one.
This is not to common (at least I like to think so) and also a real joy to figure out. I've actually had to generate proof of this by having a server call itself from two paths (one PRI or SIP or whatever to another PRI or SIP or whatever). I would play 1000hz@0db (milliwat) from one direction and then 2500hz@0db from the other direction. Add in some scripted audio analysis and you have all the proof you need. It's pretty hard (or ballsy you could say) if they insist it's your problem when a waveform of a solid tone looks like the stock market graph.
I wont even go into routing issues. That's a whole other ball of wax
Going to this extreme is probably somewhat overkill for your situation though. I would vote you wait till the new circuit is delivered and see how it sounds over that. The one good thing about Verizon in the greater Tampa Bay area is that if they need to move wires they build a whole new circuit.