As x-man suggest, test with an analog phone to be sure you can dial one of your faxes.
I like to put a butt set on line and listen as the fax system dials. You can figure out a lot of things just by listening.
But, having said that, the reason I asked if you were using analog lines is because every time I'm had this issue it was with analog lines.
Here's what happens, the fax goes off hook and dials the number before the line is ready to receive it.
I needs a few milliseconds of a pause before it dials the 9 or the PBX will miss the 1st digit.
With a butt set you may hear that.
Ralph