At first, I had the same problem. Then I discovered that you can ZOOM OUT on the map. Once zoomed out I saw all shrines, exits and marked locations.