I recently discovered a warp option in photoshop (under transform) that lets you bend aspects of your image. I think this would straighten your border out. But, even if you can't straighten it out, its still a really cool map and the curve actually fits with the idea that your adventurer made this map while travelling.