Yes agreed the menu is there, but I had another menu from a Widget, where does a Plugin widget store it’s information?
Depends on what plugin it is. If it’s a well written plugin, it would have moved the widget to the ‘Inactive Widgets’ section with all your data in tact.
As for the theme, it’s likely a file called archive.php or category.php that ceases to work. If you have a previous version that worked, start by reverting those files. What theme are you using, anyway?
(Sidenote: For things like menus, it’s good practice to use core functionality as much as possible. Sometimes plugins aren’t updated and a WordPress update can totally break them… which leads to a lot of effort fixing problems that shouldn’t exist in the first place)