Unfortunately, I´ve run into problems when it comes to multilingual sites in combination with Joomlart templates. With sh404sef things just don´t work right.
sh404sef is definitely a serious and good extension, but seems to work best (i.e. out of the box and without tweaking and adjustments) on monolingual sites.
Thanks for your positive comments. I have spoken with jimie and understood what happened to you. There is no issue in sh404SEF with multilingual sites, actually we were probably the first to support this new feature in Joomla.
What happens in your case is that you created a multilingual site, but disabled additional languages and ran it as a mono-lingual site.
sh404SEF "pretends" that the language filter is always enabled, even if it is not in the Joomla plugin list. This is why some of your menu items disapeared, as they were not in the site default language. Just using "All" for these menus items language solves the issue.
In next release, I have added a setting to explicitely enable/disable multilingual support and avoid this sort of behavior, which is correct, but might not be expected.
Please note that we haven't anything linking this to the templates you are using.