Yes you're absolutely right. I just looked quickly; polyfit doesn't work when there are repeated (or nearly repeated) xdata points.
Is it feasible to average all of the repeated xdata points so that you just have 2 vectors with 1 function value for each x value? Then you can use polyfit with that data set. It seems to me like it might produce something reasonable, but I'm not a statistics expert.
If so, you can use accumarray to perform the averaging.
If you are talking about a linear line, you can calculate the linear regression of Y as a function of X. Because it works when random errors are added to Y, there can be multiple Y values for the same X value. Alternatively, the principle component that can be calculated through the data set.