pip install python-debian should fix it

would like to add on, make sure that you run with python 2, as the script isnt compatible with python3.
I would make sure that the default python is python2 (it really should unless you changed it) but also make sure that 'pip' is linked to python 2 pip.

Mine was linked to the python 3 pip, and I dont even want to talk about how long it took me to realize my mistake

EDIT:
Sorry, I meant to leave some help for new-comers.
if your having this problem, and 'pip' links to the python3 install, try this:
python -m pip -V

If you've got installed properly, you should get something like this:
pip 9.0.1 from /usr/lib/python2.7/dist-packages (python 2.7)

If you dont, then pip for python 2 isnt installed, you ought to be able to install it with this:
sudo apt-get install python-pip

Now, to install the debian package, just run:
python -m pip install python-debian

For me, this:

python -m pip -V

produces

pip 18.1 from /home/tal/anaconda3/lib/python3.7/site-packages/pip (python 3.7)

and

python -m pip install python-debian

runs just fine, and I'm no longer getting

ImportError: No module named debian