Eu tinha um problema semelhante. Para mim, não podia chmod o vínculo simbólico, mesmo como raiz, independentemente de como eu chamava chmod. Para acrescentar confusão a isto, o nautilus estava a mostrar o dono/grupo como nada. O dono estava apenas em branco. Então eu tentei mudar o link simbólico usando o nautilus como raiz, já que o chmod não estava funcionando e o nautilus caiu!!
Mas eu acho que descobri o problema. O directório que o link simbólico estava a apontar tinha permissões diferentes do que o link simbólico. Por isso chmod'ed o directório alvo (usando -h) para o meu nome de utilizador/grupo. Então chmod'ed o link simbólico para o mesmo e funcionou! E ver os detalhes do link simbólico no nautilus (com as permissões da raiz) agora já não falha.
Então para outros que tenham um problema semelhante, verifique as permissões do directório/arquivo de destino e certifique-se que é compatível com as permissões para as quais está a definir o link simbólico.