The monitor has two inputs: DVI and RGB. I have it connected to the video card (ATI 4850HD) via the RGB. On the video card end, I use the adapter that came with the video card which converts RGB->DVI (I'm guessing).
What leads me to think that it is a Windows Update related problem is that I had no problems with the video mode for the first full year that I had it set up this way. It wasn't until a Microsoft update about 2 or 3 months ago that I began to have problems, and only intermittently. Even through the RGB port (and adapter) the monitor is recognized correctly as a Samsung Syncmaster with the correct display capabilities, so I can't see how it could be a communication error with the monitor.
Would it be worth it to invest in a DVI to DVI cable? (The only reason I didn't up to this point is that as-is the picture quality is fantastic). Couldn't hurt I guess, eh?