A site exists, let's say "search.com", and having your searches leaked is bad. A victim opens up a new browser (no HSTS from existing connections) and goes to search.com. An attacker MITMs this HTTP request and injects their own session cookies and then redirects to https://search.com. At this point, let's assume full-domain HSTS kicks in and no more HTTP/MITM are possible.
Now the victim is on https://search.com, lock icon and cert are a-OK. But the user is signed in as attacker. The user might not notice this, and makes searches, which are now available to the attacker, in the attacker's history.
Problem: Fix this, without overly relying on the victim noticing they are signed in as the attacker. After all, they just opened search.com for the first time and aren't expecting to be signed in (though they are wary of HTTPS and do notice the green URL bar).
Perhaps it is slightly contrived and the answer really is "Well, always look on a site to see if you're logged in as someone else". But otherwise it seems rather difficult to fix, outside of HSTS preload. (And this ignores all the other issues noted in the paper.)