The addon has been updated to v 3.6 and is pending Mozilla's review to go public, you can still download the latest v 3.5 from Mozilla at -https://addons.mozilla.org/en-US/firefox/addon/10137/versions/, this update makes it work again with newest Youtube changes which broke the video downloads.
An updated version of simple, fast and easy to use popular Firefox Youtube video downloader addon "Easy YouTube Video Downloader 1.2" is now available for download, the addon adds non-intrusive video download links in FLV, 3GP, MP4 and HD qualities next to video on Youtube pages.
