Not sure I can give you a solution, but am experiencing nearly same exact problem. Just curious, did you find a solution?
I suspect that my problem does not have anything to do with frame buffer rate. I'm using a triple-boot machine, and my Acronis bootloader accesses Mint 7 on partition 9 correctly. However, when I set up another OS (PCLOS 2009.2) root on partition 7, and placed the grub boot code there, when I select it from Acronis, I get the same message that you got ('/boot/gfxmenu: file not found', in my case).
I've logged in as root to Mint on partition 9, and investigated both sets of gfxmenu files. In the case of Mint, there's a folder named 'gfxmenu', and a file in it named 'linuxmint.message', same as yours, that is a 'CPIO archive' of some sort. Opening it with 'Archive Manager' reveals 10 files inside, including back.jpg, the Mint default background that I'm using, and timer_a.jpg, some sort of timer display that I believe shows during the boot-up process. The PCLOS setup is similar, yet different in some respects. There is no 'gfxmenu' folder, but there is a file called 'gfxmenu', and it is also a CPIO archive. Looking inside it reveals 73 objects, including the two files named above. back.jpg is the default background, and timer_a.jpg looks (to my eye) the same as in Mint's. There are a few dozen file pairs that appear to be language related (e.g. da.tr, da.hlp, de.tr, de.hlp, en.tr, en.hlp, etc.), and those files account for the much larger file count.
On the face of it, it appeared to me that everything was referenced correctly in the grub menu, in terms of the names of the files and their locations on the selected hard drive. What I suspect is that during the PCLOS install, grub referenced the wrong drive, as Mint refers to '(hd1,8)' (partition 9 on my second hard drive), whereas PCLOS refers to '(hd3,6)' (partition 7 on my 4th(?!) hard drive). The partition numbers are correct (grub counts from zero, so '6' is really the 7th partition (using 'human' counting from 1), and '8' is really the 9th partition). I have two installed hard drive, and one USB drive, and everything should be referencing the 2nd hard drive, where all my linux partitions have been placed - which grub numbers as '1' under Mint. I suspect a reference to my 4th (nonexistent) hard drive is incorrect, so I've changed the '3' grub uses for PCLOS to '1' in menu.lst, and hope (pray) that fixes the problem.
I'll post back here after I test it. From googling the error message, I see that I'm not the only one with this problem! I've checked fstab, menu.lst and device.map files on both systems, and can see no reason why grub should be numbering drives differently in one setup than in the other (assuming both distros use the latest grub release). (The UUID problem is more difficult to verify, I assume those refenced - in both installs - are correct, at least, the swap partition (which is the same for both) is referenced the same in each install. I tried using 'vol_id --uuid' in a terminal to see them, but the command did not work for me.
Success! The drive numbering problem I described above was the culprit! I can now boot to any of the three operating systems, and even switch from one partition's grub menu to the other partition's grub menu. I made a name changes to the gfxmenu file (making it 'gfxmenu.message', similar to 'linuxmint.message' in Mint), and also put it in a folder named 'gfxmenu', so that the architecture of the two installs is the same. Now, I just hope that a future distro update doesn't disturb the changes!