It appears that the youtube-dl-gui package does not check and install all dependencies.
When run In a terminal:
$ youtube-dl-gui
$ No module named wx
To fix this run:
$ sudo apt-get install python-wxtools
The menu selection YouTube Downloader should now work.