I'm not super familiar with that model of xbee (is that the 802.15.4 series? or the ZB series?)
But have you checked that the channels match (ATCH)
Or the A1 and A2 settings are set so that you can jump channels to associate?
What is the result of the Association Indication (ATAI)?
The return status of that could tell you what is keeping them from linking up?
Do you have at least one of them in the X-BIB dev board, or something that you can use the X-CTU software to talk to?