Thanks for the help Ross. As you suggested, the following seems to have worked for me:
1- Export the contacts from the source account
2- Export the contact groups (labels) from the source account
3- Create the contact groups in the target account
4- Export the contact groups (labels) from the target account
5- Fix the contact group IDs in the contacts export from step 1
6- Import the fixed contacts into the target group.
I wrote two scripts to help automate this, though they are not very clean, nor very tested :
Bash script:
Python script for fixing contact group IDs:
Thanks,
Mohamed.