Once that is working, go into Entourage Preferences and goto "Sync Services", put a check mark in the "Synchronize contacts with Address Book and .Mac" and in the "Address Book:" drop down box I chose "Contacts [DSG Exchange Server]"

Now in iTunes under iPhone Info I have my Contacts sync setup as follows:

Now for Calendar in Itunes under iPhone Info I have my Calendar sync setup as follows:

After completing these steps, sync your iPhone and you should now have your contacts on your iPhone. Works great for me, hopefully it will work for you as well!