I have experienced a similar problem intermittantly when I was using a phone extension reel, I would start the freedom dialer (in my case) and it would come up with the same message, "there is no dial tone". Incoming calls would get busy tone. I proved it to a break or short on one leg in the extension reel !! I'm not saying that yours is the same cause but it does sound similar. I expect you've replaced the lead that plugs into the PC modem port and the line socket?

__________________
After re-reading your post it sounds more like a line card fault on the primary multiplexer which is in the cabinet. Do you know if they have changed this? If they have then I would request a change of EN or LEN (line equipment number) this would at least eliminate the line card and exchange from the equation.