If I had a Nokia mobile I would have definitely tried this site out.
It let you sync address book, calendar and other content online to a website called ovi. I don't know if it does over the air, but there is a software similar to Nokia PC suite that you can download and do it via the PC. The content that you can sync mostly depends on the features your phone has. Once you sign in for a free account you can choose which Nokia mobile model you have and sync it.
As far as I can tell, its a free service, unlike apple's mobile me service. So go ahead and give it a try. I wish someone comes up with some thing like this for an iPhone that's free.