For the Samsung S4, I went into my Application manager, selected the youtube app, and then manually forced it to stop by clicking on the "Force stop" button. After that, I turned off the "Show notifications" setting. I then exited the Application manager and started the youtube app, and the ugly little icon was gone! I actually went back in and turned the "Show notifications" back on after this, and then flipped back over to my youtube app just to make sure that the icon hadn't appeared (which it hadn't). But I won't be surprised if this problem crops back up once I turn the phone off and back on again (or perhaps after another youtube update).