Well it works now.
I think I figured out that you can't power the Fio with the USB cable. That's only for charging (like the instructions say). I powered the board with a FTDI breakout board. But this didn't fix the problem at first.
First I had to upload a sketch over the FTDI cable (which means removing the wireless card). After that it started uploading sketches over XBee.
This is good news but it's also annoying because connecting via FTDI means soldering on the header pins, which I wanted to avoid. Oh well, better than not working.