yea, syncing contacts from one phone to another can be a real nightmare and
depends on both the point of origination and the target device.
As an example, Yahoo mail can not export contacts in ANY form
and iPhone can only sync via iTunes and is release dependent - -
BOTH really stink.
One would think that exporting to CSV and Importing CSV would be the
common, universal technique, but it's just not so.
Back to your issue, look for alternatives on both ends.
Start with the new phone and discover what CAN BE imported, and then
see if you can export in that format and/or convert from that to a form that can be imported.