Have you recently upgraded WP too, perchance? Was it a straight migration, or did you reinstall WP and copy over the theme and data? Was the menu
really working before the migration, or did you just not notice it and are assuming that it's to do with the new server?
A bit of delving suggests you are using a theme authored by 'mg12' (site: neoease.com). A Google for "neoease menu" threw up this as the 7th result - the screenshot here confirms that you're using this theme:
http://wordpress.org/extend/themes/inoveThe 3rd "see what others are saying" discussion talks about menu problems, with an author-suggested patch:
http://wordpress.org/support/topic/inove-menu-not-compatible-with-wp-32Suggestion - get a development environment for your site. Don't commit any changes/updates to the live site until they've been thoroughly tested in the dev environment.
Then push live, and test thoroughly again.