Since the same HDMI cable works fine with another machine and same Pi machine works fine with another monitor, my conclusion was that there is a software setting which should be fixed.
I tried to update my packages (
sudo apt-get update && sudo apt-get dist-upgrade) and this did not work.
Then, I have just overridden the
/boot/config.txt file. This did work. Since my screen is a 7" HDMI Display with Touchscreen, from AdaFruit, I just went to their website and overridden the
config.txt file with the recommended settings.
Basically, the lines which are not commented out are:
hdmi_cvt=800 400 60 3 0 0 0
Taken from here.
Then I rebooted my Pi and it work.