The fact that ic-prog doesn't find a calibration value suggests it has problems reading from the pic. This also causes verify to fail. The writing may also fail, but there is no way to test it because you can't read.
Have you programmed other pics before with your programmer hardware/ic-prog? (16f84, 16f628,.... ?). If not, then the 12c509 may not be a good chip to start with. It is a OTP chip, wich means it can be only programmed once. Afther each (failed) attempt the chip could become unusable. It would be better to get a flash chip (16f628 or so) to test your programmer with as it can be rerwritten over and over again.
If you HAVE already successfully programmed pics then some more information would be welcome. Like what kind of programmer hardware you are using?