I'm moving my system from an old drive to a new one, I followed the steps described here (Configure Linux kernel and grub on external drive):
chroot /mnt
dpkg -l | grep linux-image-.*-generic | sort -k3 | tail -n1 | awk '{system ("sudo apt-get install --reinstall " $2)}' #Reinstall Linux kernel packages there (credits: see https://askubuntu.com/a/298855/232047)
update-initramfs -u
grub-install
grub-update
And checked that it seems to at least be able to boot and load grub on another computer, so the main problem here is actually the BIOS which does not recognize the new device as valid (it doesn't even load GRUB on the current laptop).
Both the old drive and the new one are MBR and use grub i386-pc, so I wonder what could be causing this? I checked that I was able to boot on a live CD with an old Ubuntu 11.10*, but it does not boot with any newer Ubuntu live CD versions (for kind of like 1 or 2 years now that I think of it). So is there something that changed on recent grub versions that this old BIOS doesn't like?
Note: both Ubuntu 11.10 and newer live CDs seems to use MBR with efi, at least there's an efi folder on their boot partition, which is pretty weird (why MBR with efi?).
(*): I installed the old live on the new drive to make sure it's not the drive itself that is being rejected. As I said, the old live was able to boot perfectly.