When you make an API request, use the X-GData-Key request header to specify your developer key as shown in the following example:
X-GData-Key: key=<developer_key>
Include the key query parameter in the request URL.
http://gdata.youtube.com/feeds/api/videos?q=SEARCH_TERM&key=DEVELOPER_KEY
^^ Прямо изо рта лошади. Вам не хватает заголовка запроса X-GData-Key.
Кажется, ключ необходим как в URL, так и в заголовке, поэтому, учитывая ваш предыдущий код, попробуйте это:
req = urllib2.Request(youtube_search_url, encoded_params, { "X-GData-Key": '<developer key>' })
f = urllib2.urlopen(req)