Just want to point out that simple re-formatting, and removing and redoing partitions may not always be the same thing. Removing all partitions on a drive _should_ also remove the partition table (where I suspect the problem may be). I would suggest fully removing all partitions (with command line fdisk if you are comfortable with it), rebooting (important to commit the partition table), and then adding a new fat32 partition and doing a full format on it (not quick format).
The reason for this is that I've seen drives that have 2 completely different partition tables on them, which causes big confusion on some hardware. Some hardware reads the newest one, some read the previous one.