Here's the fill statement from YouTube:
"Microsoft and YouTube are working together to update the new YouTube for Windows Phone app to enable compliance with YouTube's API terms of service, including enabling ads, in the coming weeks. Microsoft will replace the existing YouTube app in Windows Phone Store with the previous version during this time."
At the time of writing no YouTube app from Microsoft is currently available in the Windows Phone Store. It's likely that the old version will reappear in the next few days as an intermediary option while an updated app is developed. Those who have already downloaded the app should be able to continue using it for the time being. Those looking for a similar experience would be well advised to check out the third party MetroTube app.
The restrictions imposed by the use of web technology based APIs were exactly what caused Microsoft to complain in the first place. As we previously noted the issue appears to be about a lack of API equality between the Windows Phone and Android platform. For example, there is no equivalent of the Android YouTube Player API, which allows native apps to playback YouTube video streams, including adverts, without having to use a WebBrowser control component or equivalent (i.e. not having to embed a web browser within the app).
There are two likely scenarios here:
Firstly, it is possible that Google may have agreed to provide an equivalent to the Android YouTube Player API for Windows Phone, something that would not be difficult to do. Any Windows Phone app using such an API would qualify as "using a public YouTube API" and would be able to be compliant with YouTube's terms of service. This scenario would see Windows Phone get a new YouTube app with a user experience similar to, or better than, the withdrawn app.
Secondly, Google may be sticking to its guns and only providing web technology based APIs. This would essentially put Microsoft back to square one. Theoretically, it is be possible to create a hybrid native-web-technology based app that goes beyond the simple shortcut approach, but such an app would almost certainly have a user experience inferior to that of the withdrawn app.
Given that Microsoft has withdrawn the recently updated app, the first scenario currently seems more likely, but as of yet there is no confirmation, and it remains entirely possible that a third way may be found. In any case we'll continue to keep you updated.