I use windows. And my installation failed with official guidance, too. Finally I installed Basemap using the following method. Although I am not sure if it will go right for you, I just offer mine.
First of all, you must have pip in your computer. (It is much easier to install, compared with Basemap and other things. And it can be used to install many useful packages.)
Then go this great link: http://www.lfd.uci.edu/~gohlke/pythonlibs/
And download the file named "basemap‑1.1.0‑cp27‑cp27m‑win32.whl".
Move the .whl file to directory "C:\Python27". (Maybe you installed your python in different disk, then change it accordingly.)
Open terminal. (Use cmd or Git Bash or something else.)
Use command:
pip install basemap‑1.1.0‑cp27‑cp27m‑win32.whl