However, the output on the Samsung monitor is absolutely garbage. It is pixellated to the point that I don't even want to look at it.
The resolution is 1600x900 (but I have tried all other resolutions as well - all with similar output)
When I connect my Windows laptop to the same monitor using DVI cables, I get 1920 x 1080 resolution and the display is crystal clear.
How do troubleshoot this?