It happened to me that sometimes ago (more or less February 2005) the USB hard disk (20Gb) from Linux worked well, but froom windows there was no chance to makes it work.
Finally I solved with Linux. After plugging the usb disk I’ve recreated the partition table with cfdisk (Win95 Fat32 0b) and then recreating the file system mkdosfs -c -F32 /dev/sda1. Finally I had to format from again from windows ’cause that program (call it Operating System is too much), didn’t recognize the usb device as formatted.
The question still remain, even now that the problem is here again and I will have to do the operation again: why with Linux I have no problem while windows fail to detect the hard disk?