I just went through one of our sites and updated every plugin and Wordpress to 4.2.2.
After upgrading I was supposed to do some menu changes, but after "successfully" saving the menu every item was cleared from the menu and it's position was reset to nothing..
I then started building the menu all over again, only to realize it kept on happening.
I've tried deactivating every plugins and changing themes to a default one, but the problem persists. Anyone had a similar experience? This happens to every menu I try editing and also new ones that I create from scratch.
Here's a video of me trying to add some menu items and assigning a position: https://www.youtube.com/watch?v=b9XLyy-Zzbw&feature=youtu.be
Unfortunately I did end up having to restore the site with a backup I took before updating, so I can't link to a live problem..
EDIT
Regarding kenno's answer that it might be a case of taxonomy split, I do indeed have a lot of shared terms.
Is there an easy fix for this, or a way to quickly loop through all terms instead of manually splitting terms one by one?