One possible reason is that Contacts will not be synced if you have not indicated your date of birth on your Nokia account. Ensure you have specified your date of birth and that you are older than 13.

This topic is valid for:

Nokia Lumia 900,Nokia Lumia 800,Nokia C6,Nokia E73,Nokia E7,Nokia E6,Nokia N900,Nokia X2-01,Nokia 808 PureView,Nokia 700,Nokia 5310,Nokia 1616