I think it may have something to do with the UEFI or secure boot? I can't find a reference to either in the BIOS?
I would not expect a computer which originally came with xp to be using EFI. I don't believe Secure Boot was used prior to windows 8.
Boot one of the CDs, Mint or Ubuntu whichever you have and after booting, open a Terminal and mount your / partition on the hard drive.
sudo mkdir /mnt/sda1 to create the mount point from the CD. Then do: mount -t ext4 /dev/sda1 /mnt/sda1. Then navigate to the /mnt/sda1 in the terminal or file manager and verify that the initrd and vmlinuz files are there under the /boot directory. If they are, that is not the problem.
Also, look in the /boot/grub/i386-pc directory to see if the core.img file is there. I have Ubuntu 12.04 installed and the core.img is under /boot/grub. Don't really know if that makes a difference or this was changed on 13.04. You could copy it to /boot/grub and check to see if makes any difference.
I don't really have any other suggestions. Maybe a lighter weight distro would work but the error doesn't indicate anything like that.