JUnit 4.11 was messing with Cucumber's execution order, which was breaking our build for bad reasons.
Switched to TestNG which doesn't exhibit this problem with Cucumber, but unfortunately (or fortunately) also doesn't support skipping on PendingException.
I'm now breaking the build for good reasons, taking out various pending-marked skips. We'll just have to fix the actual functionality.