It's possible that it just works in one direction, and by trying to sync the contacts to your computer, you remove them completely.
Before you try this, make sure there's a most recent backup with these contacts included. If syncing them doesn't work, and removes the contacts from your iPhone, there's still the option to restore from that backup.