I can reproduce what you see in the code below. Since you haven't shared your code, I can't be certain it is the same cause, but I suspect it is.
When you use plot, it connects the points in the order they are listed. If your values are not sorted, it will bounce up and down the line plotting the points. When you switch your xscale, it highlights the subtle incontinuities in plotting the line this way.
A possible confounding issue may be if your data is in a matrix. Since each column is treated as a separate series, you would actually have multiple lines, one for each column. Of course, when you fit a line to your points, you want to fit a single line to all the points. Be sure you are not calculating a fit for each column, which results in multiple fit lines being drawn.
You do have to be mindful that, when you use polyval on all the x values are sorted to avoid the first issue mentioned above.. It may be a good idea to just create your own x vector to be sure your values are what you need.
Here's what the figure looks like if I use polyval on an x vector I create that is sorted in ascending order.
p = polyfit(x(:),y(:),1);