Cucumber refuses to run tests in a random order

I have a decently sized cucumber test suite, but they currently all run in defined order. I want to run them in a random order. The cucumber docs say that I should be able to run cucumber -P --order random and have the tests be shuffled before execution. I have witnessed this as not happening. In fact, the presence (or lack) of the --order flag seems to do nothing.

What could be stopping my suite from running in a random order? I'm not running with a profile (hence the -P) so nothing should be already defined.