Ok, went to their web site and got the original pdf. Then printed it to a jpeg to have a play with the georeferencing.
Tried a standard SAf albers, but the map is centred on ~21degE (instead of 24 or 25E).
Georeffed it using points along the coast / border, but it also looks pretty horrible.
The map has been put together in Coral Draw. So its very difficult to get this correct without knowing what the original is in.
Could try contacting the author - Shaheed Russon (from the properties of the pdf).