As I said, I've tried this already. I have it now AFTER the cache. As soon as I enable the cache together with Gtranslate, I run it problems.
I can redproduce it when I access a site over the menu. Switch the language for example to spanish, access a few other sites, switch back to german (my default language). Then suddently some menus are still pointing to the spanish version, even now german is active.
I only have this problem when I use the cache.
Here a screenshot (full version: http://i47.tinypic.com/2642yr9.jpg