@Charles McIntosh really gave me the answer for my situation in that the passed in model was detached. For me what ultimately worked was saving the passed in model first... then continuing to add the children as I already was before:
public async Task<IHttpActionResult> GetUPSFreight(PartsExpressOrder order)
{
db.Entry(order).State = EntityState.Modified;
db.SaveChanges();
...
}