I finally figured it out. The GroupMembership is required in order for the contact to get to the mobile device!
Here is the missing part:
var groupMembership = new GroupMembership
{
HRef = "http://www.google.com/m8/feeds/groups/" + utilisateur.CourrielGmailContacts + "/base/6"
};
newEntry.GroupMembership.Add(groupMembership);