LOL funny that I am having the same problem on a client's PC!
This, or in my case, THESE messages indicate that the format program is having way too much difficulty formatting your drive. This "high level" formatting process only creates the logical formatting structure of the hard disk. In this case, the system will try and re-image the structure of the drive, but if it find bad blocks on the drive then it will attempt to reallocate these blocks.
The system that I was working on was doing this waaaaay too often. The format process was taking over 2 hours and in this particular case, after this amount of time it was only at 17%.
Not saying that this is what you should do, but the only way that I was able to fix it was to "low level" format the drive. This, very basically, physically restructures the disk into sectors and tracks so that the "high level" format can rebuild itself on this new foundation.
After the low level was complete I was able to re-format using the 98 boot disk just fine.
I'm sure that you know you are doing dude, and there are programs to help you through the low-level format process, but I still must warn you. PLEASE be careful with any low-level format process. This is usually done by the drive manu. and can RUIN your drive if not done properly.
-Michael