Cities in the game designated on the map as "Muslim town" need some form of disguise to enter. Disguise level high enough to enter doesn't guarantee you'll be able to communicate. If an aide with you has an appropriate language, that counts towards your total.
↑For Discoveries/Investment: Alexandria - Tuman Bay - With Arabic learned 55 Disguise = No, 65 Disguise = yes. Gear with 65 Disguise only had 17 Formality. Didn't have the gear selection to try between 55 - 65 Disguise.