Solving a newly installed application not running on Debian when you vaguely recall the app is Python

I'm using Debian Mint but all of this should also apply for Ubuntu and maybe even Mac OS X.

In my case i was installing QTodoTxt but the same debugging, and potentially solution, should apply to any application. They had a .deb package which i used to install it, and i was delighted— I wouldn't have to worry about handling dependencies myself. Indeed, it installed successfully and showed up with a nice icon in my application launcher. And launching it... did nothing.

Running the application from the command line provided some useful feedback:

$ qtodotxt 
Traceback (most recent call last):
  File "/usr/bin/qtodotxt", line 11, in 
    from qtodotxt import app
  File "/usr/share/qtodotxt/bin/../qtodotxt/app.py", line 13, in 
    from qtodotxt.ui.dialogs.taskeditor import TaskEditor
  File "/usr/share/qtodotxt/bin/../qtodotxt/ui/dialogs/taskeditor.py", line 2, in 
    from qtodotxt.ui.dialogs.taskeditor_dialog import TaskEditorDialog
  File "/usr/share/qtodotxt/bin/../qtodotxt/ui/dialogs/taskeditor_dialog.py", line 7, in 
    from dateutil.relativedelta import relativedelta
ImportError: No module named 'dateutil'

However, pip freeze | grep date reported python-dateutil==2.6.1 installed just fine, and for me it was completely useless to follow all the recommendations of uninstalling and reinstalling (apt-get uninstall python-dateutil; apt-get install python-dateutil) and the different ways of installing (easy_install) that the rest of the World Wide Web will tell you to do (this is the only site you can trust). Fortunately I stopped short of installing it from gzipped binary blob as many answers were recommending, because that way lies madness.

Instead, I took a look at the file that started it all, in the usual place for unix system resources binary applications (/usr/bin) but also revealing its path at the top of the stacktrace:

less /usr/bin/qtodotxt

And once i looked at it, the answer was in the first line:

#!/usr/bin/env python3

And now i was close enough to guess at a solution:

sudo apt-get install python3-dateutil

Apparently the Debian package manager doesn't do Python dependencies or doesn't know the difference between Python 2 and Python 3.