There are many ways to approach this problem with varying degrees of precision. However, they all boil down to performing a projection that corresponds with that of your map.
If you know that your map is of the Mercator projection variety, then the lat/long coordinates can simply be treated as X/Y, scaled and translated appropriately. That is, you would find a simple ax+b and cy+d that do the job.
If your map is not Mercator-projection (as it probably isn't if it tries to get the scale consistent, as this one appears to do) then your best bet is to assume it's an "earth-tangent" projection. (This works out OK for small landmasses.) In that case, you need to first project the Lat/Long into a three-dimensional coordinate system.
z=sin(lat)
x=cos(lat)*sin(long)
y=cos(lat)*cos(long)
Positive z points to the north pole. Positive y points to 0, 0, and positive x points to lat 0 long 90 (east) and positive lat/long are north and east. Of course you must convert to radians first.
All of this assumes a spherical Earth, which isn't exactly true but it's close enough unless you're firing long-range mortar rounds.
Anyway, once you have your XYZ, then you'll need to rotate and scale for the map. To rotate around the Z axis, just subtract the base longitude before you project into three dimensions. Do this to center your map on zero-longitude for easiest math.
Once you've done this, you'll only need to rotate the globe forward until your original map is face-front. Do this with a 2-d rotation in the y-z axis. Use http://en.wikipedia.org/wiki/Coordinate_rotations_and_reflections to figure that part out.
Finally, your x,z coordinates are going to line up pretty well with your map's x,y coordinates, for an appropriate scale/translate as described earlier.