I think you won't find animals that use rolling as their primary method. Problems is that for feet, you need a patch of relatively flat surface every footstep. For wheels, you need a continuous stretch, or you need a design that can withstand impacts. Small animals have an advantage there, as gravity isn't as harsh on them as on larger animals.
Very interesting. I kinda figured my explanation wasn't that accurate, but I think it conveyed the point pretty well that sometimes we can't get to new optimal states because every path to that state is worse than the current optimal state.