This turned out to be a problem with the Debian Squeeze bluez default configuration.
If anyone else hits this problem, disable the pnat plugin by editing /etc/bluetooth/main.conf:
DisablePlugins = pnat
Then restart bluetoothd.
$ sudo invoke-rc.d bluetooth restart
No changes were required to the PyBluez code.