I had a similar problem when installing OS3.9 and new hard drives. I thought I had a bad hard drive! As it turned out, HDToolBox seems to default to FFS INTL and a sector size of 1024 bytes. I changed this to 512 bytes and everything worked flawlessly.