Ok, first I assume that you aren't using any CFW that is spoofing 3.56 and actually are on 3.56 right? If that is true then I would recommend that you connect the HD to a PC and delete/format any partitions that are on it. Then reconnect it to your PS3 and try again. Hopefully you aren't on 3.56 v1, because you will have to send it to Sony if you are.
If you are using a 3.56 spoof CFW, be sure to use that firmware instead of the actual 3.56 or you will be locked out of homebrew for the foreseeable future.