Eu tive o mesmo problema. Fazer Clementine não usar o proxy fez as coisas funcionarem. Eu fiz assim (Korn ou Bourne Shell):
/bin/env HTTP_PROXY= HTTPS_PROXY= http_proxy= https_proxy= clementine
Você pode usar uma variante disso como parte de um iniciador para que ele funcione corretamente.