However, we did notice an existing fence which we believed showed the boundary between the two properties and that coincided with what shows in our title plan.
I think that that is the crucial point. If the line on the title plan coincides with the fence and the fence marked what you thought was the boundary then the title plan shows what you thought you were buying. Up to a point, when you buy "what you see is what you get" and that rule of thumb works both in favour of and against a buyer. It is one of the reasons for the general boundaries rule.