Backup link between gmail, facebook, twitter contacts
I believe backing up the data for the Contacts Storage and restoring it should restore linked-up contacts.  You can do this with an app such as Titanium Backup (requires root).