Comment 7 for bug 856333

Turns out this is provably an issue with libnl. Routes are being given priorities by NetworkManager but the function that does this isn't seeing all the routes it should when it tries to apply the priorities.

You can "easily" fix this by removing the routes and re-adding them with a "metric N" value attached. NM usually uses 1 for ethernet and 2 for wireless (and 3 for mobile, etc.)

E.g.
ip route del <network> dev eth0 scope link proto kernel
ip route add <network> dev eth0 scope link proto kernel metric 1
ip route del <network> dev wlan0 scope link proto kernel
ip route add <network> dev wlan0 scope link proto kernel metric 2

Except these depend on the actual network being set.

I've opened a bug upstream about the issue (linked), and I'm continuing to work to fix this.