gcc4 seems to miscompile gnome-menus at least on x86_64. The problem goes away if an if-else with two identical branches is replaced by just the branch code. http://bugzilla.gnome.org/show_bug.cgi?id=169200 has stacktraces and the patch Tell me if you need any other details.
Sorry, the if-else idea was just me being shortsighted. The problem is actually that cached_dir_add_entry is miscompiled, so that dir is valid at the entry of the function, but when we try to access dir-entries later dir is NULL. I have been unsuccessful in reducing this to a standalone testcase so far.
Turned out to be an unrelated 64bit problem