If they see you, but not vice versa, it means they are more advanced in seafaring than you. You just need to wait for the right technology to pop up for you. Judging by the turn count on your screenshot the map is just wrong. I don't check for such cases, didn't even expect it was possible.
