Eu tenho um problema semelhante Não consigo imprimir a partir do Ubuntu 12.04 para uma impressora do Windows conectada via Samba. Isso funcionou bem no Ubuntu 11.10.
A coisa que eu não entendo é que não há nenhuma mensagem de erro "real", pois diz, por exemplo, "Send-Document successful-ok". Até mesmo a autenticação do usuário funciona bem.