Check the address book options on the device and make sure wireless synchronization is set to Yes. If it is already set to Yes, try the following..
Take a backup of the device address book
Open the address book on the device
Go to options
Type rset on the device keyboard
select yes in the confirmation popup
This will delete all the contacts from the device and reloads the contacts from the outlook mailbox. Wait for about 10-15 minutes and create a new contact in outlook and see if it synchronizes.