Trying with a "High Speed" HDMI cable works!! (grabbed one today from my boss in the office) Lots of people in the forum tried changing HDMI cables but still the same problems, so I thought it wasn't the cable!
Thanks for the support, Chris! For those who have the same problem, try using a High Speed (1.4?) HDMI cable and see how it goes