O gold linker está agora no pacote binutils em vez de binutils-gold (que é o que apt-get está tentando informar). Já que você já tem o pacote, você tem o linker.
Parece que não consigo mais instalar o gold linker para 13.10:
$ sudo apt-get install binutils-gold
Reading package lists... Done
Building dependency tree
Reading state information... Done
Note, selecting 'binutils' instead of 'binutils-gold'
binutils is already the newest version.
0 upgraded, 0 newly installed, 0 to remove and 276 not upgraded
Eu vejo este com muitos avisos de 'remoção' . WTH? Eu já tentei apt-get update e não ajuda
Editar o mesmo problema acontece com o Trusty (14.04)
O gold linker está agora no pacote binutils em vez de binutils-gold (que é o que apt-get está tentando informar). Já que você já tem o pacote, você tem o linker.