All right, I just spent 30 minutes trying to figure out why my USB drive won't format.  It was simple, I had ReadyBoost turned on.  Go to properties, select the ReadyBoost tab and turn it off.  Now you should be able to format if you are in Vista or Win7.

If it doesn't format now check the web for other reasons.