RevMen: You soldered the header pins on the x-bee explorer right? A solder sucker will remove that if you need to in future. Otherwise you could use 2 header pins and put a standard PC style jumper between them. If you use right angle pins it wont even stick out too much.
You can also power the fio using a battery... the standard battery connector works a treat. It lasts a couple of hours like this (depending on how much serial work the xbee is doing i suppose). I prefer it this way because then i can have the whole thing mounted in my project, on the other work bench. It helps the imagination flow. I have even had it charging while I'm programming (although i think this is not recommended).
You definitely need to have the baud rate set to 57600, as this is what the fio bootloader is expecting. I would recommend using 57600 in your project too. Its fast enough for most things.
Are you using x-ctu to configure the xbees? I seriously recommend it! That way you can see all the possible settings etc...