Is there some kind of menu or page on Xbox that lets you browse your saved game data? (Unfortunately I'm a PS4 player so I don't know where it would be, but I believe there is something like that.) If there is, do you see any saved games or a saved player profile for NHL16? If you see some and you haven't progressed far in the game and are willing to lose that progress, you could try deleting those files. I believe uninstalling and reinstalling the game doesn't delete these, so they might still be there from the first installation time.
I've also read that some users have had problems with their games on Xbox and that doing a complete power cycle (turning the console off completely, not just putting it on stand-by) has solved the problem. This might be your first option, but the problem sounds a bit different from the ones I've read about.
