Hopefully you can find your solution in the installation tutorial Amiduffer cited. I browsed it, and it contains lots of good details. If nothing there helps, here are a few thoughts...
1) Double-check your jumper settings and cabling. Perhaps try another IDE cable. Your description reminds me of a problem I had a number of years ago, trying to format high density floppy disks with (apparently) a faulty Catweasel controller. In the end, I never got it working. It was either a bad controller or too much noise coming from the motherboard.
2) The "Automount this partition" option is available if you tick "Advanced Options" and click "Change...", but this should always be enabled by default. You said that you are setting the "Bootable" switch for your partition. Under "Advanced Options", the Boot Priority should be "0".
3) If there is a valid partition on the drive, no matter if it's formatted or not, I believe it should be viewable from the Early Boot screen. Bootable partitions should be listed to the left. This is the part that bothers me most. If you see no trace of the drive, and you immediately warm boot (Ctrl-LAmiga-RAmiga) and reenter the Early Boot screen, I assume you still see nothing?
Are you sure you have the 3.1 ROMs? The 3.0 ROMs didn't pause long enough for some hard drives to finish their initialization spin, and so Kickstart wouldn't see them initially. But a manual warm boot like above would fix the problem.
4) Don't worry about writing the FastFileSystem to the RDB. In your case, this should be the same file stored in the ROM, and so should be optional.
5) If you connect the drive to a non-Amiga computer, I assume you can format it and use it normally?
Short of a weird incompatibility or fault with your hard drive (in which case you would never have gotten as far as you describe), I can't think of anything else to try.
Good luck,
Todd