The sparkfun XBee explorer boards are not too great for XBees more powerful than the series 1 modules.
See the comments on the sparkfun page for example.
This may be what is causing the issue, especially if you have the older boards with the low power regulators on them.