So far the only common denominator for the failing seems to be the connection from your host to Vimeo. It could be something either at your host's side, Vimeo's side or in between. Do the embedded videos from Vimeo work so that the only thing failing is getting a thumbnail from them?
The Vimeo API part is documented at http://vimeo.com/api/docs/simple-api under Making a Video Request. Video Thumbnails connects with the code line curl_setopt($ch, CURLOPT_URL, "http://vimeo.com/api/v2/video/$id.php"); that matches Vimeo's http://vimeo.com/api/v2/video/video_id.output where "output" can be "json", "php" or "xml". From there it finds the contents of the field thumbnail_large.
You can try making a request on your host's command line to the same URL and see what happens. You can use wget, curl, lynx/links/elinks browser, PHP or anything you like. Just get a video id, for example use the one you pasted above: 20639284.
For example on my host the command wget http://vimeo.com/api/v2/video/20639284.php got a HTTP response 200 (= file found, everything fine) and saved a file 20639284.php. You can use a text editor or grep to seek inside that file. grep thumbnail_large 20639284.php found a long line that includes the string s:15:"thumbnail_large";s:50:"http://b.vimeocdn.com/ts/132/102/132102854_640.jpg"; pointing to the URL of the thumbnail.
wget --spider http://b.vimeocdn.com/ts/132/102/132102854_640.jpg on my host got a HTTP 200 OK response, so it finds the file no problem (--spider makes it not save the file, just get the response).
If a connection to either server doesn't work, you can try traceroute vimeo.com or traceroute b.vimeocdn.com (on Windows tracert instead of traceroute) to see the where the connection to that server fails. If you need to contact your system admin, these results can save him time in solving the situation - or you might found out it's something you should ask in Vimeo API Forum instead.