I made some progress, at least I figured out why the 'Found theme: ...'
line doesn't appear.
I ended up installing a fresh install of Ubuntu! I edited the /etc/default/grub file and installed the theme the usual way by hand (manually) (by adding GRUB_THEME and etc) and when I comment the line Grub console like this:
#GRUB_TERMINAL=console
it shows me the:
Found theme: /boot/grub/themes/*/theme.txt
line.
But when I remove the # at the first of the line, it no longer shows the found theme line.
And the thing is when I do this and reboot it doesn't show the grub menu at all, neither with theme nor without theme!
So far we know the problem is probably because of this damn 'GRUB_TERMINAL=console ' line. So with that in mind, any idea why this happens?
Seriously, I wonder why nobody has had this problem before! When I first ran into it I Googled and expected that I'll find a good link that people had this issue and somebody explained how to fix it but Probably I'm the first person who reports this issue!
Please help, no linux problem has taken me this long to fix and I've been on GNU/Linux for about 15years now and that's why it's a pain in my ass that I can't figure out the fix...