HDMI screen size does not fit

I have an external monitor connected via HDMI. If I select 1920x1080 resolution the contents of the screen do not fit. The width and height on the displayed screen are too big, so the Start menu is off screen and only see the top half of the Task Bar at the bottom. I have not had this problem on this monitor from multiple other computers.

Lower resolutions fit OK but get the "this resolution is not Optimal for this monitor" message.

I tried various Graphics settings and restarted the LP and turned off/on the monitor.

I have a Samsung SyncMaster monitor. And have Single Display, Digital Television SyncMaster selected.