There is a way around this.
I had the same thing happen to me with a 2 gig USB stick that was full even though it was nowhere near it.
The problem was caused by a fragmented and corrupt set of files that I'd put on there.
All the file headers were toast.
I couldn't delete the files either.
I solved the problem by using Hewlett Packard's flash card formatter.
I can't find a direct link to it on the web so I've uploaded what I downloaded ages ago to my own website.
They're free so there's no problems.
You can get at the programs here :
http://www.davethedrummer.com/pics/drivekey
The HPUSBFW application is a windows one and the other is a DOS one.
They both work a treat.