If your PA28 is ederly it could still have the original aluminium cables connecting the battery to the starter. These are poor conductors at best and age adds corrosion to the problem. There is a mod to replace these cables with copper ones. We had this done to our PA28 and believe me it makes a hell of a difference, the engine spins round a treat on even the coldest of mornings, while before it struggled to turn through compression.