I just set mine up yesteday (UK customer), installed all the firmware updates and youtube isn't available. I wish I hadn't installed all the updates now!
I spent ages on the phone getting through to Amazon Echo Support and explained the sutuation. I explained it was available, then got removed, then got re-instated (but perhaps only in the US so far?). Their official line to me was that YouTube isn't available - this is what they've been told to say. They knew nothing about it being re-instated or the fact that it seems to be available again in the US but not the UK. Also there is no way to roll back to the previous firmware.
Their solution: If you wanted it for yotube and it's not working you could try to return it!
Great.