Affected versions are 1.8.0 through 1.8.3p1 inclusive. Ubuntu 11.10 is not affected (it's running 1.7.4). Ubuntu 12.04 (alpha) might be, which appears to be running 1.8.3p1, for a short while anyway.
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 10.04.3 LTS
Release: 10.04
Codename: lucid
$ sudo -V
Sudo version 1.7.2p1 $ ln -s /usr/bin/sudo ./%s
$ ./%s -D9
[some debug output with garbage]
Segmentation fault
$
Bug is here:https://bugs.gentoo.org/show_bug.cgi?id=401533
Looks like it's patched on x86/amd64 already.
OpenIndiana looks unaffected. It's using 1.7.4p4.
Fedora compiles everything with -DFORTIFY_SOURCE which means this still crashes, but is not (thought to be) vulnerable. In any case there is an update available for Fedora right now. https://admin.fedoraproject.org/updates/sudo-1.8.3p1-2.fc16