Comment 3 for bug 221797

If you run:
dpkg --search _bluetooth.so

you should see:
python-bluez: /usr/lib/python2.5/site-packages/bluetooth/_bluetooth.so

Basically, you need to change:
import _bluetooth

with:
import bluetooth._bluetooth

The choice of moving _bluetooth.so in the bluetooth directory seems to be peculiar of Ubuntu.

For consistency the example files like "inquiry-with-rssi.py" should be updated with the new module path.