I'm using Windows 7 on my PC and Vista on my Laptop. Right clicking on Vista the format option is there but errors. Downloaded 'HP USB Disk Storage Format Tool, V2.2.3' but errors with 'There is no media in the specified device.' ?
I would try formatting on an XP machine whose formatting abilities are better known to me and if the error message persists I think you have a bad drive.
The best piece of advice i read was from John Van Kirk - "Many times flashdrives or even removable drives become corrupted if they are disconnected abruptly before cached data is completely written to the drive and the files are closed".