How do I get an old iOS 4.1 iPhone 3GS to sync with my iCloud contacts on my OS X 10.7.5 Mac?
If you go into the contacts/address book app on you mac, select all the contacts (either cmd-a or select first, scroll to bottom, hold shift and select last) and you can either right click or click on the little cog wheel at the bottom of the app and export the contacts to a vCard.

You can then use another free cloud service such as google or yahoo and import the contacts into that account on their website.

Sign in to this account on your iPhone and choose to use it for contacts only and they should start to all sync down from the cloud.