You should remove the previous partitions. On new usb-stics, you can find arbitrary partitions which, of course, do not work. Use
# fdisk /dev/sda
or whatever your device, delete the pre-existing carbage, make a new partition, and format it using
# mkfs -t vfat /dev/sda1
or whatever filesystem do you like.
Gurus -- are there any graphical frontends in gnome/kde?