Sync it in Windows first.

I lost an entire afternoon trying to get my new Nokia 6300 to sync with multisync and kitchensync. After trying everything on the forums I sync'd it with Windows then went back to Linux and everything worked without a configuration change.

I am guessing the official Nokia software turns on sync'ing on the phone.