when i built the pc put a hd4350 ati in from the start, thought it had onboard graphics but just had a look no socket on the computer to plug the monitor in only hdmi,dvi,dvga sockets were on the graphics card so that option looks a dead end.
Have you updated the driver recently? I had something similar happen to me at the weekend after reinstalling Windows 7 after swapping SSD drives, when I downloaded and installed the latest driver for my H D 6870 I was getting the same message on my Dell monitor. To be honest I don.t know what I did to sort it. I certainly checked all cables and seating and HDMI cable then I reinstalled Windows again but this time updated everything via Windows update before installing the latestest graphics driver. Anyway it worked. But I am not sure what it was that I did that actually worked. The odd thing was my PC seem to boot except Nothing was on the monitor apart from the error 'power saving mode'. I'll give it some thought see if I can remember anything else I tried.
Obviously different circumstances to your own problem and not really sure what else to suggest as you seem to have done the right checks.