But the MSPaint test is not quite the same thing. By pasting into MSPaint and copying from there, you've actually changed the image. Follow with me, and I'll show you what I mean.
On XP; should be in Vista and Win 7 too.... From the Windows menu, Run. Type clipbrd (this is the Windows Clipboard Viewer, around for ages, but not really given an icon these days on the Programs menu; check it on Google or Yahoo search before running if you are scared (correctly) of just running stuff from forum posts)). It may complain that the "clipbook" service is not running, which is fine.
Now, copy your first image. I copied a 1200x850 pixel image from Greenshot and alt-tabbed to Clipboard Viewer. Under the View menu dropdown, you can see, at the bottom, the different formats Greenshot has made available on the clipboard. In my case, DIB Bitmap and Bitmap.
Now, let's do what you did: past into MSPaint, and then select all, copy. Now go back to Clipboard Viewer. You'll see new options at the bottom of the View menu. Besides DIB Bitmap and Bitmap, you should also see Picture and Enhanced Metafile.
So, when you are pasting in, Paint.net can choose which format it wants to use. Some programs offer Paste Special which lets you choose the format; MS Office has this.
The fact that the large image is handled well out of MSPaint implies that Paint.net is using either the Enh Metafile or the Picture format, instead of the Bitmap format, which is all that Greenshot is setting. And it's good to know that it can handle the larger image in that format.
Still, I think there is something wrong with the Bitmap image handling from the clipboard. It's related to size of the image, and it's a new bug in 3.5 that I didn't experience in 3.3. Simply by forcing Paint.net to have only Bitmap and DIB Bitmap on the clipboard (try using any non-MS graphics program, like FreeSerif's Photoplus at http://www.freeserifsoftware.com/), it's easy to replicate this error.
BTW, when you copy from Paint.net, it also supplies only DIB Bitmap and Bitmap. Clearly, that's the format of choice for most graphics on clipboards, and so I think this bug still applies.