(brief random notes, that may help someone else)
A brief tale of getting a matplotlib and basemap to work with pyinstaller. There are two strands to this the Linux and Windows.

This is mostly the linux story.

Step by step, to how I got working.

I was trying to build a single directory solution and a single file solution.
Final conclusion was best to make the application single file and dont include the BaseMap data. then supply the basemap data separately.

This makes it easier to share the basemap data with other applications.

Dependent upon whether you are working on a machine that has matplotlib/basemap installed or not did change how things behaved.

In what follows dev_machine is my dev machine with all packages installed, the target machine is the users machine and has none of the dev tools installed.
Things needed…
On target machine it needed a matplotlibrc,
As a fiddle (thanks to this post http://ubuntuforums.org/archive/index.php/t-1506538.html) I copied my dev machine /etc/matplotlibrc to the directory in which the exectuable was stored on the target machine

the next problem was

IOError: proj data directory not found. Expecting it at: /usr/share/basemap/data

This required a tweak to /usr/share/pyshared/mpl_toolkits/basemap/pyproj
in new install ended up in /usr/local/lib/python2.7/dist-packages/mpl_toolkits/basemap

as per this post http://code.google.com/p/pyproj/issues/detail?id=40&q=PROJ_DIR

Which boils down to around line 239, replace this line

pyproj_datadir = '/usr/share/basemap/data'

with

if 'PROJ_DIR' in os.environ:
   pyproj_datadir = os.environ['PROJ_DIR']
else:
    pyproj_datadir = os.sep.join([os.path.dirname(__file__), 'data'])

The setting an enviroment variable to wherever you have the basemap data
in my setup this was in a folder where the executable was
export BASEMAPDATA=./basemap/data

Next rebuild the pyinstaller files and try again….
export PROJ_DIR=./basemap/data

just didnt work!
copied /etc/matplotlibrc from dev machine into the same folder as the executable and
it worked!….As long as I supplied the basemap data in a folder called basemap/data