Same problem here (Xubuntu upgraded from 8.10->9.04 RC). Reinstallation of Wine never helped either. Additionally the "Other" category randomly vanished and reappears from/in my xfce-menu ( I don't think this is a wine-related bug though)