Right before writing this question, I clicked on the "tools" link on the main site to see if there were questions voted to be closed; to my surprise I was redirected to the review page.
I then noticed there were two new words (on the left) where I don't remember seeing any before; clicking on the grayed-out "TOOLS", I noticed it is a link that takes me to the tools page, the one I was looking for. SE seems to remember which of the two links I clicked before, and since I didn't click on "tools" after the menu change, I was taken to the review page; the confusing thing is that I clicked on "tools" on the top bar, and I saw the URL change to english.stackexchange.com/review.
Maybe it should be more evident those are links; the same could apply for other links in the header. A dotted line under the link could help.
As an alternative, a notification that explains the change in a few words could be shown the first time a user click on the "tools" link on the top of the page; for example it could say "If you are looking for the tools page, click on the 'tools' link you find to the left side of the page." (Not the best wording, I must admit, but it's just an example.)