Tem uma outra forma para recuperar o menu do Wine.
Abra o arquivo de configuração de atalhos deletados do menu:
Digite ALT+F2
Digite gksu gedit ~/.config/menus/applications.menu
Procure por algo semelhante ao texto abaixo:
<Menu>
<Name>Wine</Name>
<Exclude>
ALGUMA COISA QUALQUER
</Exclude>
<AppDir>ALGUMA OUTRA COISA</AppDir>
</Menu>
Retire o <Exclude> e o </Exclude> de todos os componentes do Wine, ou seja, que estiverem entre o <Menu> e </Menu>.
Qualquer coisa posta o arquivo acima para que possamos dar uma olhada.
Fonte:
http://ubuntuforums.org/showthread.php?t=477108 - Adaptada ao nosso bom e velho Português.