I bumped into the reason for this change in behaviour on a German site.
Previously you could edit the value of max-redeal near the beginning of the config file and set it to -1 for unlimited redeals (as per the comment for that line). In Ubuntu 12.04 that no longer works. The code that parses the options in the new Klondike menu item, forcefully resets the value of max-redeal.
There may be a more elegant way to do this, but the simplest way I found was to edit as root (use sudo) the file:
/usr/share/aisleriot/games/klondike.scm
Near the end of the file, look for a section like this:
(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))))
Either delete, or comment out with a semi-colon, the second to last line.