I did many tests with pytube and squid today and everything worked just fine for me. I was not able to get errors that you got so I will try to explain how pytube uses proxies and hopefully this will help us to decide if there is a pytube or proxy problem.
Pytube uses Python urlib which uses http_proxy variable that should be set in your environment. When you enable proxy in Preferences->network proxy you in fact add proxy settings to ~/.gconf/system/http_proxy/%gconf.xml and make it accessible for many gnome apps via gconf. That is why pytube works fine when you run it in gnome-terminal (gnome-terminal will fetch those settings) and will not run when you use pytube from menu as http_proxy is not set then.
If you want to have http_proxy set in your environment(not only for "gnome environment") you might consider adding:
In order to test if your environment is ok you might use wget to try to fetch some website when http_proxy variable is set. If this works and pytube does not, then there is a bug in pytube that I cannot track at the moment so please report that and I will try to hunt it down. If wget also does not work, than your proxy settings or proxy configuration are not right.
please try to launch pytube in terminal and report if it solves this problem.