I have two sites on a WP-MU install running the Twenty Eleven theme. The random header image works fine on the parent site, but (maybe since WP 3.5?) not on the child (previously was working fine). If I have random image selected, no header image displays. I can, however, select any single image and it will display fine so it doesn't seem to be a path issue.
Your help is greatly appreciated.