The exact error message, after making the boot selection, "was"
Uncompressing Linux...
crc error
--Sytem Halted
I wonder how many messages with CRC error are possible but anyway here you have.
Oh, and I said "was" because the problem was solved in the most unexpected way possible! These days my machine had an upgrade of memory from 512M to 1G. I know many people will think I'm lying, but the fact is that, after doing that, GRUB simply started working as if it have never had any problem.
Thanks for the interest!