Maybe there is an issue with the gateway(hardware, or firmware), without a second one to test with, you are not left with a lot of options at this point. Did it work correctly in the past, or is it new? Is it running the latest firmware? If it is, and it allows, you might try going back to the previous release, just to see what happens. You don't seem to have much to loose at this point.
The only other thing that it might be,(and I have seen things like this), but it is long shot, is that the piece of hardware (CLASS service card) in the central office switch, has an issue. It might be that it is being sent at a low level, still enough to be detected by your caller ID device, but not by the gateway. If your lines come from a "remote switch" , then there is more likelihood that all will be affected. If you are close to the host switch, then there more of a chance that each line equipment will be assigned to a different "part" of the switch so the issue would not be happening on all lines. Of course that will also depend on the line capacity of the switch and where you line equipment was assigned.
You did try calls on more than one line, right?
