So we iterated. One thing is that we should assume our users are at best paying partial attention to the interfaces we design. The lack of attention means they are likely to miss smaller changes in the interface.
Practically, anything we can do to make changes more obvious will help them. For example, using color changes and animation helps draw attention to the change. Reducing the number of elements (stimuli) users have to process provides another way to focus their attention.
In our case we decided to show both warnings at once instead of switching out warning messages. This way, when a user fixed an error, the effect of their action was easier to notice. Instead of a change in text, there was now one fewer warning message on the page.
This change dramatically improved user comprehension. With both issues visible together, users could easily see what still needed to be fixed.
