Syncing iPhone 3G with iCloud
Its easy:  

Go to: setting > Mail, Contacts, Agenda   and "add a new account".
Choose "other"
Then add "CardDav-accounts" under "contacts" tab 

In the server field first fill in: contacts.icloud.com
Then you apple id and password, then add or save account.
Then the server address will change to something like:  p02-contacts.com

Next step is to know what unique apple ID you have, you can find it here on your mac:

~/Library/Application Support/AddressBook/Sources/&lt;iCloud Account ID&gt;/Configuration.plist.

Now, go back to the just created account on your iPhone for your contacts and change the server address field. 

Contact server: https://p02-contacts.icloud.com:443/&lt;uniqueid&gt;/carddavhome/

You have to add everything above, so https://&lt;your correct server&gt;:443/&lt;your uniqueID&gt;/carddavhome/

Before you do all this you have of course setup iCloud and make sure that you have address book checked. Also make sure you have deleted your MobileMe account on the iPhone first if you have one. 

It might take some time but it will work.