I'm having a similar thing on my current game. I own Venice, Serbia and Greece and have a line of ships through to Egyptian lands and also had ships to Constantinople, but I can't see into some other factions' provinces - despite their not being another ship in the same sea area as me. I'm pretty sure that was when I hadn't moved ships around for a while too.

On a related matter, I can't build a trading post in Serbia (and I think Greece from iirc). I thought you could build trading posts in all provinces? Or id that a false memory?