I also experience this problem.
I played with it a bit more and noticed that some videos actually have a link that is good for adding to the playlist, i.e. it will play. However after some time later (when the playlist is finished playing and probably plus some time out) the playlist becomes worthless, i.e. the links become broken.
So my impression is that in order to use the playlist feature, youtube is somehow tracking your session, where session id is embedded in those "correctly" added to the list links.
I guess, the fix will require correctly following the youtube session rules: perhaps maintaining the session variable and replacing the session id in the video link whenever it times out.

Can you give some examples of links which do and don't work please?
You could try uninstalling gst-ffmpeg, and updating to the latest version of gst-plugins-bad.

(In reply to comment #2)
> Can you give some examples of links which do and don't work please?

http://www.youtube.com/v/o3oFPnN_vwg
http://www.youtube.com/v/rEBevB4ifv0
http://www.youtube.com/v/Se7ZoMyZh44
http://www.youtube.com/v/xEnGRGaMhYs

> You could try uninstalling gst-ffmpeg, and updating to the latest version of
> gst-plugins-bad.
I checked the versions of the gst-plugins-bad, maybe i try updating via sourcecode 

via sourcecode: (0.10.7)
via apt /synaptic (0.10.6-5)

---------------------------------------------------

if i remove gst-ffmpeg, then it's possible to add videos to the playlist, but a error is displayed, concerning no flash-plugin-installed... the video don't work

i reinstalled gst-ffmepg and realized that the video i try to add, is found in the playlist but the errormessages goin on.  

<b>totem without gst-ffmpeg:</b>

** (totem:7369): DEBUG: Creating object of type YouTube+TotemPythonPlugin
** (totem:7369): DEBUG: Creating Python plugin instance
** Message: don't know how to handle application/x-shockwave-flash
** Message: Error: A application/x-shockwave-flash decoder plugin is required to play this stream, but not installed.
gstdecodebin.c(792): close_pad_link (): /play/decodebin0:
No decoder to handle media type 'application/x-shockwave-flash'

** Message: Missing plugin: gstreamer|0.10|totem|application/x-shockwave-flash decoder|decoder-application/x-shockwave-flash (application/x-shockwave-flash decoder)
** Message: don't know how to handle application/x-shockwave-flash
** Message: Error: A application/x-shockwave-flash decoder plugin is required to play this stream, but not installed.
gstdecodebin.c(792): close_pad_link (): /play/decodebin1:
No decoder to handle media type 'application/x-shockwave-flash'

** Message: Missing plugin: gstreamer|0.10|totem|application/x-shockwave-flash decoder|decoder-application/x-shockwave-flash (ignoring)
** Message: All missing plugins are blacklisted, doing nothing

I must admit that I use totem-xine, hence no gst messages in the terminal.

But anyway:

this is the link that works (plays when double-clicked on a search result):

http://www.youtube.com/get_video?video_id=aPBzfo9sj1Q&t=OEgsToPDskIUwv2OJXToHH9GBF4YZARL

and this is the link that gets added to the playlist and does *not* (while choosing with right-click, add to playlist):

http://www.youtube.com/v/aPBzfo9sj1Q

If you move mouse over search results you can see the URL in a tooltip text, and some (very few) of the results may contain the former type of links, they work when adding to the list but they seem to expire (something to do with parameter t?). I could not find a pattern which and why.

Most of the links are of second type, are playable only via double-click and if you "add to playlist" such a link it will refuse to play with a popup "there is no plugin to handle this movie" and message in terminal:
demux_wavpack: (open_wv_file:127) open_wv_file: non-seekable inputs aren't supported yet.
[flv @ 0xb5e045b0]warning: first frame is no keyframe

I apologise if it's a different bug than the originally reported.

I just checked with totem-gstreamer and I get the originally reported messages on
http://www.youtube.com/v/aPBzfo9sj1Q :

** Message: don't know how to handle application/x-shockwave-flash
** Message: Error: Element doesn't implement handling of this stream. Please file a bug.
gstffmpegdemux.c(1416): gst_ffmpegdemux_sink_activate_push (): /play/decodebin1/ffdemux_swf0:
failed to activate sinkpad in pull mode, push mode not implemented yet

I think it's a link miss-handling, i.e. this link should be converted into http://www.youtube.com/get_video?video_id=aPBzfo9sj1Q&t=OEgsToPDskIUwv2OJXToHH9GBF4YZARL form upon play, otherwise totem is getting 
[application/x-shockwave-flash] which is a shockwave-flash embedded object and not the video stream.

Ah, I see now. This is because the YouTube URLs need resolving into the video ID URLs before they can be played, and this is only done when they're double-clicked. If you right-click and add a video to the playlist before double-clicking it, the wrong URL will get copied to the playlist.

This is done because it would be very slow to resolve all the URLs when loading the search results, but it may well be a necessary slowdown.

I am not convinced about the "slow" argument.
The Internet lookup is not neccessary, look, the substitution is trivial:
1) get/maintain parameter t (session id?)
2) extract the movie id from the original link
3) sprintf(newlink, "http://www.youtube.com/get_video?video_id=%s&t=%s", id, t)

Step 3 is in C and it runs faster than blink of an eye :)

Of course this is Youtube specific and binds to this specific URL "API", but hey, we are talking about Youtube plugin :) and still the links are unlikely to change.

I am still worried about the parameter t -- if that is a session id or some kind of timeout timestamp, then we better do a substitution as late as possible: i.e. during "add to playlist", or ideally just before the playback.

I think fixing "add to playlist" should be trivial and without *any* performance penalty even with Internet lookup (you will have to substitute the link at some point anyway!). And fixing "substitute just before playback" will probably require to rethink the whole plugin-playback-codec framework (it would be nice that the codec would do this substitute, but I guess codec does not assume Youtube website) but this would also allow you easy drag-and-drop links from Firefox... just my guess :-)

Playlist is essential feature here, because playlist feature is messed up in Youtube interface, so totem would be a perfect alternative. 
Please don't make it minor, it's an "add to playlist" feature that is broken :)

2008-07-09  Philip Withnall  <philip@tecnocode.co.uk>

	* src/plugins/youtube/youtube.py: Resolve the video URI of YouTube
	videos when loading search results, rather than when playing them
	to ensure URIs added to the playlist are correct. (Closes: #541916)

(In reply to comment #7)
> I am not convinced about the "slow" argument.
> The Internet lookup is not neccessary, look, the substitution is trivial:
> 1) get/maintain parameter t (session id?)
> 2) extract the movie id from the original link
> 3) sprintf(newlink, "http://www.youtube.com/get_video?video_id=%s&t=%s", id, t)

I'd committed the patch before I got your message. Anyway, when the plugin was originally written, we looked briefly into the video URL business, and found that it was probably best to let YouTube provide us with the canonical SWF URL, as it knows best. If you want to analyse the t parameter and give a complete and reliable implementation which generates its own t parameter, feel free, but I'm afraid I don't have the time. Substituting the parameter in is easy, but working out how to generate it is unfortunately less so.

Yes, you are right, Youtube knows best.
I've looked at HTML source and t stands for session token, and such links become "ERROR 410: Gone."
So it looks like cat-and-mouse-chase game in order to track user and/or avoid session hijacking... and probably leads nowhere unless we emulate javascript which is equivalent of playing it in a browser :(

I have one more idea:
Current double-click does the following:
1) looks up the stream link from video id
2) adds it to the playlist
3) forces totem to jump to the end of playlist and play it

Now I am not sure about the "jumping to the end of list", but it would be nearly perfect procedure without step 3 to implement "add to playlist".

I think this should work at least for an hour or so (until session token t expires or gets corrupt due to too many link lookups until the movie actually gets played).

Maybe I'll get some time over the weekend to learn python and hack this one...

Thanks for you effort.