How can I correctly set DJANGO_SETTINGS_MODULE for my Django project (I am using virtualenv)?

Don't run django-admin.py for anything other than the initial project creation. For everything after that, use manage.py, which takes care of the finding the settings.

I just encountered the same error, and eventually managed to work out what was going on (the big clue was (Is it on sys.path?) in the ImportError).

You need add your project directory to PYTHONPATH — this is what the documentation means by

Note that the settings module should be on the Python import search path.

To do so, run

$ export PYTHONPATH=$PYTHONPATH:$PWD

from the ~/dev/django-project directory before you run django-admin.py.

You can add this command (replacing $PWD with the actual path to your project, i.e. ~/dev/django-project) to your virtualenv's source script. If you choose to advance to virtualenvwrapper at some point (which is designed for this kind of situation), you can add the export PY... line to the auto-generated postactivate hook script.

mkdjangovirtualenv automates this even further, adding the appropriate entry to the Python path for you, but I have not tested it myself.