The problem is a bug in the model Mage_Core_Model_Url_Rewrite_Request (Magento 1.8) and Mage_Core_Model_Url_Rewrite (earlier versions).
The section of core code in 1.8 looks like this:
// Section from Mage_Core_Model_Url_Rewrite_Request::_rewriteDb()
$fromStore = $this->_request->getQuery('___from_store');
if (!$this->_rewrite->getId() && $fromStore) {
$stores = $this->_app->getStores();
if (!empty($stores[$fromStore])) {
$store = $stores[$fromStore];
$fromStoreId = $store->getId();
} else {
return false;
}
The Bug: the value of the query parameter is the store code, (in my case de, en or fr).
The keys of the array returned by app->getStores() are the numeric store IDs.
Thats why if (!empty($stores[$fromStore])) { always fails.
Once that bug is fixed, another bug becomes apparent later in the same method (I think only in 1.8):
$targetUrl = $this->_request->getBaseUrl() . '/' . $this->_rewrite->getRequestPath();
The request objects base url always is the Magento base_url, without the store code.
Using $currentStore->getBaseUrl() instead there fixes that bug, too.
Once those two issues are fixed the language switcher works fine. Here is an extension which does exactly that for Magento 1.8 (CE): https://github.com/Vinai/VinaiKopp_StoreUrlRewrites
In Magento 1.7 the issue might be something different. I still thought I'd add this answer, just in case google brings somebody else here who is running 1.8 or newer.
The answer is the following:
Only one menu is needed, so you create your menu under Catalog -> Manage Categories at the language that you are going to set as default,also remember to give at every menu item url key, then you change store view and rename those menu items to whatever language you want to use, you have to rename the url keys too. Every menu item item should also have a url in the all store view scope. And after that you are done. Everything works just fine.
Best Answer
Make sure you set the right homepage for each store view under
System->Configuration->Web->Default Pages->CMS Home Page. Make sure the page you set for each store view is active in that store view.