NOTE: As of June 1, 2011 the current Ubuntu One contacts sync for mobile will no longer be active. We’re stopping support for our current service so we can focus our energy on launching a much better service sooner than we could otherwise.
Probably not the answer you were looking for. I am Ubuntu (3 PC, only one dual-boot) and Android ( 2 Android phones) user myself.
I will recommend migrating to google contacts. I suppose all of your contacts are stored in "Phone" (if you are not syncing them) Most phones can easily export your contacts to a SDcard and then re-import them. When asked, select your google account, not "Phone". You should select only google contacts to be visible, to avoid duplicates.
If you want to sync your desktop mail app with online service, and you use Thunderbird (or you are OK with it), installing zindus will provide sync between thunderbird and gmail contacts. G contacts and android contacts are auto-sync with the correct options anyway.
To sum it up:
If you want a simple online solution, select google contacts (gmail)
If you want an offline desktop app mail client, add Thunderbird +zindus to the equation