I recently spent a lot of time trying to change the firmware and parameters on a programmable XBee with a Sparkfun explorer + arduino. I spent a lot of time with it, trying to get XCTU to recognize it, but nothing helped. I got the "press the reset button" pop up screen, or a "This radio module is programmable" message. However, I could get the bootloader to work when connecting through serial. Even though XCTU would never recognize it. I tried downloading the legacy version, downloading the SDK and uploading a different firmware to it, but none of this worked. I had some other XBees and I could read the parameters but could not update the firmware. I thought that it had been bricked, and was pretty close to throwing the towel.
Finally, I asked a friend for a parallax USB adapter and it worked perfectly well. In case someone is stuck in my same situation, I believe that the problem is that the arduino is incapable of running reliably at 115,200 bps through software serial. So, if you're not running hardware serial, and trying to get to update the application, it will break down. I did not try using the arduino UART ports (pins 1 and 2 on the arduino UNO), since I got the parallax adapter, but I believe that this might help some users solve the issues. I also had to run it in Windows, for some reason my installation of GNU/Linux did not work well with the parallax adapter. The programmable module came (directly from the store) at 115200.
So, this isn't really a question, I'm just hoping that if someone gets extremely frustrated with the modules and searches the forum, they'll find this answer and can try a different way of programming them, as arduino + XBee explorer can have reliability issues that are not mentioned clearly.