The objects I've seen working with Random Anim Start only have texture transform controllers (like the oasistorch), no location/rotation animations. I haven't been able to find one that has both (like the arc) and Random Anim Start checked. That might be an issue.
If you find one that physically moves as well as the texture moving/changing with random anim working, might be able to narrow it down.