"When I changed the boot device priority in the BIOS such that the linux HD was before the other one, I got the following message" searching for boot record on IDE 1.....GRUB "
This is what you would expect when booting the Linux disk because you did not install any bootloader on the MBR of this disk.
"Right now, I install the bootloader on the first sector of the boot partition(on the samsung drive)"
Something went wrong with this install of the bootloader. I do not know what.
To solve the problem use the rescue mode of your install disk. Boot the install disk and select the rescue mode. tell rescue to boot your Linux system. Once you are in your Linux system you can repair grub.
Or you can read the links and then reinstall Red Hat paying close attention to the bootloader install.