In my opinion, that automated warning is applied in three different situations.
1. The first is what you originally assumed - just letting you know about the situation, but no traffic loss will result. Doing nothing is the best bet here.
2. The second occurs when the notice is soon followed by ranking and traffic losses. Then I think it's time to break out the Disavowed Links tool and Reconsideration Request - unless the traffic lasses are something you can live with.
3. The third is when things get really dire. Massive traffic losses show up and when you examine the backlink report, you see a vision that's quite hellish with link manipulation programs. You have a big job on your hands here, and may need to abandon ship. It can be worth giving it some energy, but maybe not too much.
I've seen all three of these situations, but Google doesn't tell you where you stand specifically. It's something each affected webmaster needs to work for themselves.