When we reviewed Tube Download, we found an application that does what it sets out to do, even if the Windows Phone OS does get in the way a bit:
It's important to note that because of the silo'ed nature of Windows Phone applications, these videos are not directly available in the Videos section of the Media Player - they will (forever and a day) only be available through the Tube Download application.
This isn't as painful as it might sound, because media applications are well integrated across Windows Phone. Tube Download appears as a media application in the Music+Video hub, and any videos or playlists that you have watched with Tube Download will show up in the 'new' and 'history' lists (handily with their caption in a blue title strip at the bottom of the tile so it's clear where they came from).
You can download the latest version of Tube Download from the Windows Store on your handset, or the AAWP App Directory.