Please provide a link to your site so we can check what may be going on.
Did you check your settings in Main options > Menus to see if they did change?
Also assuming you created your menu with WordPress Custom menus, did you check the Custom menus in Appearance > Menus to see if the primary or secondary menu allocation is still the same?