To summarise, in understanding this problem we must not ignore its inherent observation selection effect. This resides in the fact that when we randomly select a driver and ask her whether she thinks the next lane is faster, more often than not we will have selected a driver from the lane which is in fact slower and more densely packed. When we realize this, we see that no case has been made for recommending that drivers change lanes less frequently in order to speed up overall traffic flow.
It seems like cars in the next lane really do go faster, at least according to Nick Bostrom, a lecturer at Yale who wrote this post on maths.org.