It sounds like your proxy requires credentials. Credentials have to be supplied in code; I'm currently trawling the source for the Google API to find it, since they have their own custom request objects.
In the mean time, you might get it to work by simply not using the default proxy. Modify your app.config or web.config to insert this at the correct location:
<configuration>
<system.net>
<defaultProxy>
<proxy usesystemdefault="false"/>
</defaultProxy>
</system.net>
</configuration>
Edit:
Ok, after doing some digging, here's how I think you'd refactor the instructions you linked for your specific request. Assuming you've already created a YouTubeRequest as follows:
YouTubeRequest request = new YouTubeRequest(settings);
Here are the refactored instructions from your link:
YouTubeRequest request = new YouTubeRequest(settings);
GDataRequestFactory f = (GDataRequestFactory) request.Service.RequestFactory;
IWebProxy iProxy = WebRequest.DefaultWebProxy;
WebProxy myProxy = new WebProxy(iProxy.GetProxy(query.Uri));
// potentially, setup credentials on the proxy here
myProxy.Credentials = CredentialsCache.DefaultCredentials;
myProxy.UseDefaultCredentials = true;
f.Proxy = myProxy;
Here are my sources:
http://google-gdata.googlecode.com/svn/docs/folder56/T_Google_YouTube_YouTubeRequest.htm
http://google-gdata.googlecode.com/svn/docs/folder53/P_Google_GData_Client_FeedRequest_1_Service.htm
http://google-gdata.googlecode.com/svn/docs/folder19/P_Google_GData_Client_Service_RequestFactory.htm