Respondido pelo launchpad
A documentação em /usr/share/doc/libcurl4-gnutls-dev/html/curl-config.html está errada, e, portanto, este é um bug da documentação.
Em vez disso, ou lendo na linha 88:
'curl-config --cc --cflags --libs' -o example example.c
deve ser lido
'curl-config --cc --cflags' -o example example.c 'curl-config --libs'
Isso coloca as bibliotecas compartilhadas APÓS o objeto que queremos vincular e agora funciona.