Eu encontrei o motivo dessa mudança de comportamento em um site alemão.
Anteriormente, você poderia editar o valor de max-redeal próximo ao início do arquivo de configuração e defini-lo como -1 para redeals ilimitados (conforme o comentário dessa linha). No Ubuntu 12.04 que não funciona mais. O código que analisa as opções no novo item de menu Klondike, redefine vigorosamente o valor de max-redeal.
Pode haver uma maneira mais elegante de fazer isso, mas a maneira mais simples que encontrei foi editar como root (usar o sudo) o arquivo:
/usr/share/aisleriot/games/klondike.scm
Perto do final do arquivo, procure uma seção como esta:
(define (apply-options options)
(set! deal-three (cadr (list-ref options 1)))
(set! deal-one (cadr (list-ref options 2)))
(set! no-redeal (cadr (list-ref options 3)))
(set! max-redeal (cond (no-redeal 0)
; (deal-one 2)
(#t -1))))
Exclua ou comente com ponto-e-vírgula, a segunda à última linha.