Update: Google has released a new YouTube app for Android which allows videos to be downloaded and stored in a permanent fashion on the device. I don't think that it is necessary to comment this.

How convenient that they decided to start shutting down services that download videos/mp3 from youtube while launching an app to do exactly that