I found that it takes about 48 hours for new node information to fully propagate throughout the Lightning network, and that payments may fail before that propagation is complete.