I have a new BSE 40GB ATA100 IDE harddrive that I am trying to install
in a older AMD K6-400 computer. I believe the BSE drive is actually a
Maxtor OEM drive.

Anyway, I ran fdisk and partitioned the drive into two equal (16GB)
partitions. When I try to format either partition, the format starts
normally, but quickly I get a message saying, "Trying to recover
allocation unit," and a countdown.

Does this mean the harddrive is bad? Does it mean the harddrive is
too large for this older machine? Is there any way around this?

The harddrive arrived with no documentation or drivers.