I've had the same thing happen to me on an old Toshiba laptop. Bought a new HD, fitted it but the computer couldn't make heads nor tails from it. The BIOS on laptops doesn't always have the full options to recognise a HD, in those cases the HD type is hardcoded somewhere in the machine.
I've managed to solve the issue on my laptop by switching HD brands. The drive that came out was an IBM, it wouldn't recognise a 6 Gb Toshiba, but when I switched it for a 10 Gb IBM it booted up without any problems. I did need to install a drive overlay to 'fool' the BIOS, but many HD manufacturers have this software available from their websites.
Something similar may be the case here, so if you've got the option to try a different drive (I took my laptop with me to the store and fitted it there) try getting the same brand as the one that came out. If that doesn't work, and the BIOS doesn't have any drive parameters to set, then you can probably only exchange it for the same type again.