Menu edits do not appear immediately

Go to the global settings page: http://www.example.com/?q=admin/themes/settings
Edit the primary links and secondary links html.
Click Save Configuration.
Note that the links for your site have not changed.

Workaround:
Go to the theme specific settings page for your site: http://www.example.com/?q=admin/themes/settings/yourtheme
Disable primary and secondary links.
Enable primary and secondary links.
Note that the links have now changed.