Joe,
Typical drain on C cell batteries is in the range of 100 milliAmps. Your 4.5V 700mA power supply should have more than enough power to work if connected with the correct polarity.
I'd suggest verifying the polarity of the power supply and the coin sorter. Polarity on low voltage power supply connectors and jacks is not universal In other words, some are center positive and outer negative and others are the opposite.