Check the lid on the pump basket (make sure it is clean and tight). What kind of cleaner do you have ? I have a suction side cleaner and have had problems in the past with small holes in the flex tubes drawing air.

Also look at the pump basket after it has sat turned off for a while. Is it still full of water ? It sounds like you are losing prime.