Hi;
If your line protocol is down then it is a layer 2 problem more than likely no clocking from the CSU/DSU or mismatched LMI which is a teleco problem. Try to shut the interface down and bring it back up. If the protocol comes up but goes down in 40-50 seconds you are not getting LMI's from the provider. Do a "show frame-relay lmi" and you should see the sent and recieved LMI's going up when you bring the interface back up.
Try to do the following loopback tests to determine problem.
1)Place local CSU/DSU in loopback mode. Check the line protocol it should be up. If not problem is cable or CSU/DSU.
2)If ok contact the provider and have them put their end into loopback mode. The line protocol should again come up. More than likely it will not so you will know it is on their end.
My bet is that the telco changed something and they have their LMI-Type or something set wrong. Remember that on some of the newer IOS the LMI is autonegotiated and that could cause you grief. If you do a "show int sX/X" where X is your interface it will show you the frame-relay LMI type:
LMI enq sent 431592, LMI stat recvd 431570, LMI upd recvd 0, DTE LMI up
LMI enq recvd 0, LMI stat sent 0, LMI upd sent 0
LMI DLCI 0 LMI type is ANSI Annex D frame relay DTE
Notice that the LMI recived and sent are nearly the same and that the LMI type is ANSI Annex D. Hope this helps.