I've ran into this problem when trying to FAT32 format 64gb Kingston Usb Key and this is what worked for me

Skip step 1-4 if your usb key already has an assigned drive letter.

1. Log on as administrator or as a member of the Administrators group.
2. Click Start, click Run, type compmgmt.msc, and then click OK.
3. In the console tree, click Disk Management.
4. Create a new partition or a new logical drive for your USB drive and manually or automatically assign a drive letter
5. Download: http://www.ridgecrop.demon.co.uk/download/fat32format.zip or here: fat32format.zip
6. Extract the single EXE file to somewhere suitable, like C:.
7. Click Start / Run and Type: "cmd".
8. CD to the where you extracted the fat32format.exe
9. Type fat32format X: (if your usb key is X: drive)
10. You should see this displayed: Warning ALL data on drive 'f' will be lost irretrievably, are you sure (y/n)
11. Type: "y" and press Enter.
12. Wait till format finishes.
13. You're Done! :)

I've tested this formatting 64gb usb key, where Windows format and every partitioning solution I've tried failed.