1. Get supported video mode info
(to achieve this, I had to install hwinfo)
>sudo apt-get install hwinfo
Then check supported modes (I was interested in setting the resolution to 1280x1024 and set the highest color depth available, so I'm going to check this.)
sudo hwinfo --framebuffer |grep 1280x1024
The best available mode was shown like this
> Mode 0x031b: 1280x1024 (+3840), 24 bits
> Mode 0x0345: 1280x1024 (+5120), 24 bits
Strange as it is, 0x0345 worked from the above two modes only.
2. Edit /etc/default/grub
sudo nano /etc/default/grub
Uncomment #GRUB_GFXMODE="some value", and change it to your resolution, also add GRUB_GFXPAYLOAD_LINUX line, like in the example below. Also modify GRUB_CMDLINE_LINUX_DEFAULT to reflect the video mode chosen.
Save the changes you have done.
3. Update grub
If all went smooth, Ubuntu will boot in the resolution you set, for me 1280x1024x24 was fine.
Finally I managed to refine this solution, it's not partial any more.
If connecting with putty, cygwin, you will not experience this issue and the settings above will not change your terminal experience.