I believe you are saying that the labels ('Home', 'Contact Us') are changing, but the links ('/', '/contact-us') aren't. The way Zend_Menu uses Zend_Translate only for the menu labels.
If your menu is created by MVC instead of URIs, you can make it take your language values by adding the line
$page->setParam('lang', Zend_Registry::get('Zend_Locale')->getLocale());
This would go in your navigation render, between "foreach ($page as $subpage) {" and "echo".
If your menu is using URIs, you can do a substitution on the page HREF at the same point.
Now, if I've misunderstood your question, and it's not translating links OR labels in the menu, then check and see if your menu is executing before your plugin's preDispatch.