We have a PRI being brought in on a 2851 router running 12-4-15-T5 code. It is configured as an h323 gateway. The controller shows up clean and the serial interface shows layer 2 going up and down. When I do a "sh isdn status" it shows it in TEI_ASSIGNED and after a few seconds goes to AWAITING_ESTABLISHMENT and after a little while it goes to MULTIPLE_FRAME_ESTABLISHED. After being in that state for a few seconds it fails back to TEI_ASSIGNED and goes through the same process again. I have included a debug isdn q921 in the attachment.
If nothing has changed in the configuration from when it was working and you have replaced all of the hardware on your side, it has got to be a provider issue. That would have been the most likely issue to begin with, but considering the troubleshooting steps you have taken, it is the only possibility left.