Then you aren't doing it properly due to my crappy explaination, Or there is something inherently wrong with your app and I would suggest a reinstall in that case.
But I think I'll just explain this more easily..
Because I'm SERIOUSLY listening to music on it RIGHT NOW while I type this.
Once again, you WILL get the error if you go on the default page of the app.
In other words, that page that says "reccomended" and "popular" and all your "watch laters" is what will create the error.
As far as the "ad" is concerned, its very tempermental because I'm not sure whether the ads are the same on every box, or for that matter that there will always be one leading to youtube.
But my point is that if you can find a link of some kind, that is linked to a youtube channel such as the one I clicked, which oddly enough had to do with andy milinokas and his rap battles, then you will skip the main page. By doing this, you avoid the 4004 UNLESS you go back to that home page.
If you are getting 4004 in the middle of videos, then it is not related to this issue. This is because this does not happen to me or any one else I know and therefore is an exclusive problem.
Other than that, I am CERTAIN that if you do not come across the main youtube page, you will not experience that instant 4004.
Lizuka if you are still getting that error, then you are doing it in a way that still goes through the home page and need to find a different way in. Once again, you might not have a youtube ad in your video panel.
On my xbox, where it says "youtube" in this image is where the ad is. Only its not a youtube logo its like the cover image of the channel.

[Once again, it won't look like this as this dash is much older, but where it says "youtube" is where the link was. I wonder if it only shows ads based on apps you have. if you guys are seeing something different that might be why but I'm just speculating.]
I would imagine though, that currently all of our ads are the same. So the youtube link I used should be there for everyone.
So once again, find this, select it, wait for youtube to start booting up and you'll start in a channel with a bunch of its videos there, featuring a fat lil rapper white kid lol.
From there press Y and search.
I HIGHLY doubt that by some miracle that only I can do this. If I can do this, all of you should too.