I just had the same problem.
I had a "fresh" Ubuntu install (16.04) with python 3 only.
Then I followed the steps to run SITL and also checked all the dependencies as khacyr listed.
Still did not work.
So, to find out what was wrong, I issued this command in the mavproxy console window (yes, thank you perterbarker!):
set moddebug 3
module load map
this gave me an error with some clues: libjasper.so.1 was missing!
Could not install it "easily" on Ubuntu... apt-get install libjasper-dev did not work
So I installed it directly from a debian package (from here: https://packages.debian.org/jessie/libjasper1 and one of its dependencies that were missing also from here: https://packages.debian.org/jessie/amd64/libjpeg62-turbo)
To install directly, I did
sudo dpkg -i libjpeg62-turbo_1.3.1-12_amd64.deb
sudo dpkg -i libjasper1_1.900.1-debian1-2.4+deb8u3_amd64.deb
and the map works like a charm!
I do not know why this dependency failed to be picked-up... maybe the devs could include them somewhere?
Just would like to register here to try to help the next guy.