Have you set up the xbee's to use the same channel?
If not, take a look at this:
http://www.ladyada.net/make/xbee/configure.html
Scroll down to the "Configure with XCTU" part of the page (it's the program I prefer to use - gives you a sort of gui for selecting what options to change)