Consegui deletar de forma indireta.
Então o que eu fiz... abri o Nautilus como root (sudo nautilus) e fui até a pasta /home/usuário/Desktop
Se clicar com o botão direito, não tem a opção de deletar, mas tem a opção de Recortar.
Então criei uma pasta na pasta pessoal e colei o tal atalho. Depois deletei a pasta que continha o atalho dentro.
Assim deu certo.