About 2 days ago it started doing that to me too, on ALL my devices. These are all devices that, months ago, were added and clicked to NOT ask for it again on that device. Just out of the blue it started asking for it, even on my main computer, EVERY TIME I log in.
When I first signed up for Two Step it worked fine UNTIL a couple of days ago. This is getting REALLY OLD.
NO cookies have been deleted, so this is NOT a cookie problem. This is clearly an Amazon problem.