I have a slightly newer verison of List::Util here (1.63 as below) and sample appears to work as intended, ie. different runs produce different results:
$ pmv List::Util
1.63
$ perl -MList::Util=sample -wE 'my @x=("a".."z"); say sample (3, @x)'
jso
$ perl -MList::Util=sample -wE 'my @x=("a".."z"); say sample (3, @x)'
ter
$ perl -MList::Util=sample -wE 'my @x=("a".."z"); say sample (3, @x)'
mgl
$ perl -MList::Util=sample -wE 'my @x=("a".."z"); say sample (3, @x)'
ago
$
There's nothing in the List::Util changelog to indicate any modification to sample so either some other fix has had an effect or something else is at play.