You need to save the menu name first when you create it. After which you can add menu items to the menu.
There may be issues with a conflict on the name of the menu. The database updates with WordPress 3.8.1 may have not update. Try updating justre-updating Wordpress, if that doesn't work, and it isn't an issue with plugins then go to the database parts of WordPress 3next paragraph.8
Also for me the issue always comes down to File Permission errors.1 See here http://codex.wordpress.org/Changing_File_Permissions The File Permissions may be causing issues. Make sure the CHMODs are correct and the CHOWNs are correct (I generally make the CHOWN the same as the one that runs apache (or nginx, etc). CHMOD is file read/write/execute permissions and CHOWN is who owns the file.