Hi: I also had same problem as described by ballombe. I first noticed the problem when I found that all the menu tree under 'Debin' was gone (in K menu). So I manually run the 'update-menus' and saw the same error messages.
After added the '-' and '_' to the 'genmenu=' line in those two files relating to freedesktop staff (as suggested by ballome), update-menus finished without any complaint, and all the Debin menu tree was back in K again.
