I'm having the same issue. I have checked "display from personal albums" and it's still only showing media from galleries. The albums, and album media, is viewable by all (even folks not logged in) but they're still not showing up.
If I change it to "latest media" they'll show up, but not if I've selected "random media".
I'm thinking there might be a bug here, or I'm simply missing something. You shouldn't have to batch update anything to for images that are viewable to show up on a widget.