I do think that the sea-route travel times could maybe use some adjusting. Fissoa-Madina, with no unit, is 16.8 miles per hour. Could it maybe be bumped to 20mph?
That's already fast for a boat. Caravels (already late middle ages boats) didn't go much faster than 10 mi/hr (ref:
http://wiki.answers.com/Q/How_fast_in_knots_did_a_caravel_ship_go).
20 mi/hr is something you get with a small motorboat. Barring storm conditions, I doubt you can get that with a large sail-powered boat. Small catamaran-types boats probably achieve that in good condition, but they are used for sport, not transportation.