Same problem here; when I print out handouts 2-slides-per-page in landscape mode and then photocopy them for lectures, I very often lose the left-hand edge. After some experimentation this evening, I've found a fairly simple solution which works for me, though.
It's true that in Leopard, "Page setup" has gone from Keynote, but it's still there once you hit "Print", under "Page attributes" in the drop-down menu that's headed "Keynote". There you can choose the paper size and, more's the point, make a custom paper size.
Go to the bottom of "Paper size" and hit "Manage custom sizes"; you can create a new paper size (A4 for me, i.e. 210x297mm) and in principle change the margins individually.
However, if you do the obvious thing, i.e. increase the left-hand margin to 2cm (say), while leaving the other three at their defaults, Keynote behaves badly and increase all margins to the same 2cm. Or something like that; it's not 100% obvious, but it does fairly clearly shrink the whole thing down, rather than simply pushing things to the right, as desired.
However, after some futzing, I found a solution. Instead of changing the margins, make a paper size which is the same width as A4 (210mm), but shorter than A4 by a couple of centimetres (e.g. 280mm). Leave the margins as the defaults and then print.
If your printer behaves the same as mine (an HP LaserJet 4250), it'll probably protest and tell you to load this new custom paper size. You can override this, however, and just tell it to print on whatever is available (i.e. A4). The printer then prints the job on a virtual 210x280mm piece of paper centred on the real 210x297mm piece of paper and, hey presto, leaving a nice 2cm or so margin on the left-hand edge, as desired.
Seems a bit long-winded, but since you can store this new "A4 Keynote" (for example) paper size, each time you come to print your handouts, just select that paper size under "Page attributes" and print. Yes, you may need to hit the enter button on your printer to force it to use real A4, but that's easier than opening a second program, I reckon.
Hope this helps.