Have you tried booting into recovery and clearing the system cache partition? Not clearing all data, i.e. a factory reset - that's an option if nothing else works, but make sure you have everything backed-up before doing that - but sometimes clearing the system cache can resolve issues like this, and incompatible data in the cache is more likely after a major update. Of course not all phones have a cache partition these days, but if yours has that might be worth a shot.
Otherwise, all I can say is could you tell us which major update this is? Different phones receive updates at different times, and I've known devices receive a major update (i.e. new Android version) more than a year after it was released and after other devices are already on the version that replaced it. Hence not having your device most of us probably don't even know which android version you have been updated to.