Reported here https://github.com/bitcoin/bitcoin/pull/12629#issuecomment-381095603 by @Empact.  I've seen it now in a few different travis jobs, including:

https://travis-ci.org/bitcoin/bitcoin/jobs/366157920
https://travis-ci.org/bitcoin/bitcoin/jobs/366139851

From my initial investigation it seems like there may be an actual bug in block announcement, so I'm  opening this issue to track.
CFeeRate oldFeeRate(mi->GetModifiedFee(), mi->GetTxSize());
                if (newFeeRate <= oldFeeRate)
                {
                    return state.DoS(0, false,
                            REJECT_INSUFFICIENTFEE, "insufficient fee", false,
                            strprintf("rejecting replacement %s; new feerate %s <= old feerate %s",
                                  hash.ToString(),
                                  newFeeRate.ToString(),
                                  oldFeeRate.ToString()));
                }
                for (const CTxIn &txin : mi->GetTx().vin)
                {
                    setConflictsParents.insert(txin.prevout.hash);
                }