I have a new install and set my album thumbnails to RANDOM, but they do not change when I reload the page.

I have another install where the thumbnails random as they should on every reload.

Is there something I am missing somewhere?

http://www.droneshutter.com/gallery/

At least if you are not logged in that makes sense as you have the static_html_cache enabled.