You need to update all your packages. The latest MiKTeX package manager seems rather broken. If you use Task > Update Wizard, you’ll probably meet “The update wizard could not be found”
The solution is to open the Update program directly (type “Update” in Start Menu or find
miktex-update.exe. I used both the normal variant and the “(Admin)” variant. A couple of updates later it’s finally working!