You have to make sure the art is assigned to every singe song and not just some of the tracks. iTunes will make it look like every song has the art applied in CoverFlow, but if you do Get Info and look under the Artwork tab, you may find certain tracks are missing art. If this is the case, the iPhone will not display art for those tracks.