We frequently get questions on this topic due to varying server configurations, so here are some things you can try:
First publish the default Joomla main menu module to your site and with SEF URLs turned on see if the menu causes the same errors as the built in suckerfish menu that our templates include. If so then you know that its not a template issue but configuration problem with your server/Joomla.
This place provides several methods for troubleshooting SEF URL problems with Joomla:http://www.scribd.com/doc/2300167/Joomla-v-15-Configure-and-troubleshoot-SEF-URLs
Some tips from Joomla:http://docs.joomla.org/Why_does_my_site_get_messed_up_when_I_turn_on_SEF_(Search_Engine_Friendly_URLs)%3F