It is a strange bug. I tried to look at different map sources. You are really near the border on the Google maps (16 meter) and 3 km away on the OSM map.
I found the what assume is the official province borders linked below and they are almost the same as the osm data.
It looks like its possible to place a cache on land on the edge of the peninsula that Prince of Wales Fort is located and it is in Nunavut. See the osm map.
It looks like the border is less the 1 km out from the shore beside the city of Churchill
I would not really trust the google province borders. I have in Sweden logged one cache on a region border a few meter from the border sign and it was 11 km from the border on google maps.
It looks like the regions borders on PGC is the same as the OSM data and the cache should be located Nunavut.
I looked at the images
https://dl.dropboxusercontent.com/u/27625662/Geocache/churchill%201.jpg
https://dl.dropboxusercontent.com/u/27625662/Geocache/churchill%202.jpg
The black line is the border according to the kml file in the link below.
It is closer to land then the OSM border, On the second image you can see that the border is on land really near churchill.
This assumes that the KML import in JOSM is correct. And that the data in the file is correct and has the necessary accuracy
http://geogratis.gc.ca/api/en/nrcan-rncan/ess-sst/b754e4f9-3cdc-439e-9b4a-9aecd057a244.html