Yea, that sounds like an air leak and BigDave's suggestion is a good one. The pump should fully prime at full speed or even near full speed. Have you noticed any change in the filter pressure since you have been having this problem? You can also reduce the suction on the pump by keeping both the main drain and skimmer fully open.