Resolvido
Nas Configurações Avançadas de Compartilhamento (acessadas através do painel esquerdo na Central de Rede e Compartilhamento), escolha 'Ativar o compartilhamento de arquivos para dispositivos que usam criptografia de 40 ou 56 bits'.
Parece que o samba não suporta criptografia de 128 bits (ou eu não o configurei para fazer isso)