Zyb.com is a great service, and I have been using it for a long time (nothing worse than loosing all your contacts or having to copy them to the SIM card when moving between phones) but unfortunately the doesn’t have an Android client, and I have been unable to make any other clients work.
There for I have been working on a zyb importer, which can import JSON files with your contacts, which zyb makes available from zyb.com/feeds, the project can be seen at code.google.com/p/zyb-import, I will try to make the application available via android market as soon possible, until then you can download the source and build it yourself.
See screenshots here.
Update: the app is released to android Market, search for “zyb”.
Update 2: the app only works with android 1.5 and 1.6, I was planning a new version supporting 2.0+, however, zyb has in the meantime announced that they will close down on the 31st of July, I will not make an updated version, I thus urge anybody with android 2.0 or greater to use the method described here: http://www.consumingexperience.com/2009/05/zyb-export-copy-mobile-phone-contacts.html for importing their contacts, before it’s too late! Thanks.