Minitube is a native Youtube client for Linux that can play and download Youtube videos without any use of Flash.
A new version of Minitube has been released (version 1.4) that adds support for Youtube channel search with autocomplete and suggestions.
You can download Minitube by running following commands:
sudo add-apt-repository ppa:ferramroberto/minitube
sudo apt-get update
sudo apt-get install minitube
[Thanks to Ferramosca Roberto for the PPA]