I also find this a problem. I usually get a base screenshot from software apps and work on them to make design sketchs.
I guess you changed your picture resize management algorithms for zoom or compression, or something like that, I think I didn't have this problem at previous versions of MS Visio.
And, sometimes, at 100% zoom it still doesn't look clean. If I double click the image, it gets opened at Paint... and there it looks clean! So... Why it has to look so bad at Visio? I think you should have this in mind and try to fix it, there are a lot
of reasons to work with base pictures at Visio.