Thanks, that's what I thought :/ However then I read some product descriptions of some cables on Sparkfun that said even though they were 5V they could be used with 3.3V boards like Lilypad, etc. For example this:
So I started to think I might be able to get away with it and the Fio might tolerate 5V. I'm not going to risk it though. I was in a rush, should have read the description more carefully...