The 3 keys with newspaper ads are size (yours is adequate, if not larger than needed), frequency (do it a minimum of 3 to 5 times in a row before making any judgement as to its effectiveness) and reach for $ or CPM (Cost Per Thousand). Another can be paid vs free delivery, as many free papers are not as well read as free, though those that get the free ones tend to lean a little more towards a local service person.
Your CPM seems very good, I wonder if the 40,000 they gave you as a munber is hoe many are delivered vs how many "read". This is often a sneaky trick that the ad reps use, bringing in the pass around factor in a household. If only 20,000 are delivered but thewy say 40,000 "read" it they are implying that 2.5 people read it at the delivery location. Use the delivered as your basis for analysis.
Ken