Bitsafe needs a device of at least 4 gb with decent write speed.
To check for USB sticks speed go to http://usbflashspeed.com/ and
aim for device with at least 10 MB/s of *write* speed, the more
the better.

If you own one of these, you should be ok:

Lexar JumpDrive Lightning II
Transcend JetFlash
OCZ Rally2 Turbo
Corsair Voyager GT (rugged!)
Silicon Power LuxMini 920
Sandisk Cruzer Contour

For SD cards, you should aim for a Class 6 (40x) at very
least, better a Class 10 (66x).

Raccomanded size: Bitsafe uses about 250MB for binary and 3.5 GB for
persistent storage, so you'll need a 4 GB key. Anything over is just
wasted.

TL;DR: Look for the fastest 4GB drive you can afford to buy.