As for "working out of the box", is there a way to test this? If I restore the default values, what do I need to do to see if they are communicating to each other?
I assume you have the XBee carrier board (a serial or USB to PC). You can set the Coordinator destination address to the Router/End Device's 64-bit IEEE address number (consists of SH & SL in the XCTU). This can be done in the XCTU program. Then connect the Router/End Device to a PC. Use a terminal program to send out test data continuously (1 second maybe). Short the RX and TX pin of the coordinator. You should be able to see replica of what you send on the terminal program.
By using this method, you eliminate the mistake that you might have made on a microcontroller (coding, wiring, etc). Once, this is okay, you can move on to incorporate the Arduino into the setup.
Again, I understand the RX/TX thing, but I'm not sure I understand what you mean about the baud rate. I know that both Xbee's need to have the same baud rate... was there anything else you were referring to?
The baud rate refers to the serial interface baud rate between the Xbee to the host (Arduino, PC). So, both the host and the XBee must have the same baud rate. You can have many XBee, but not all of them must have the same baud rate. Communication between XBee modules is fixed at 250kbps.
Here's a link to common mistake when configuring an XBee:
Common XBee Mistakes