Multiple rlib candidates found on beta/nightly, but not stable

On Travis-CI, I'm testing my multi-crate workspace:

This has worked fine with path-based dependencies. Tonight I published these two crates here to crates.io, and as such needed to specify the dependencies differently. Now, I get errors on Travis for the beta and nightly channels, but not for stable. I don't really understand what's going on here.

Any suggestions? Is it possible there is a regression in cargo or rustc?

I've now filed https://github.com/rust-lang/rust/issues/39879 about it.