I never tried to use this on 360 but I assume you'll have to format it with your 360 first.
Yeah, when I try to format it, it fails. But then I have a cheap little sandisk cruzer micro and it works fine.
Reading quickly online, all I could find is a sentence saying most USB flash drive could work, but doesn't define which ones.
IIRC, the Xbox can only support 8GB.
I have the 8GB and you're allowed pick how much of the drive you format.