Removing wine completely from Ubuntu:
$ sudo apt-get --purge remove wine
$ sudo apt-get autoremove
$ sudo rm -r ~/.wine
You can remove the following files but not necessary:
/usr/share/app-install/desktop/wine.desktop
/usr/share/app-install/desktop/wineconfig.desktop
/usr/share/app-install/desktop/winefish.desktop
/usr/share/app-install/icons/_usr_share_pixmaps_winefish-icon.png
/usr/share/python-support/guidance-backends/wineread.py
/usr/share/python-support/guidance-backends/winewrite.py
/var/lib/python-support/python2.5/wineread.py
/var/lib/python-support/python2.5/wineread.pyc
/var/lib/python-support/python2.5/winewrite.py
/var/lib/python-support/python2.5/winewrite.pyc
Never use rm if you don't know what you are doing
I don't know why the menus still there in gnome but everything else has been remove. If you don't want to see the menus go to System -> Preferences -> Main Menu and remove it from there.
If later you want to reinstall wine first renable the menu in gnome by going to /home/username/.config/menus you should find a file - applications.menu . Inside should be similar to this:
<!DOCTYPE Menu
PUBLIC '-//freedesktop//DTD Menu 1.0//EN'
'http://standards.freedesktop.org/menu-spec/menu-1.0.dtd'>
<Menu>
<Name>Applications</Name>
<MergeFile type="parent">/etc/xdg/menus/applications.menu</MergeFile>
<Menu>
<Name>wine-wine</Name>
<Deleted/>
</Menu>
</Menu>
If so delete the file. (if there's more than the wine entry I'd try just removing the wine ref.) There may be other wine related .menus in the applications-merged folder, delete them also. Now you can reinstall wine.