This problem is caused when two contact numbers are given out by the system to two different users.  To resolve the issue you need to:
  1. Go to Tools > System Utilities > Set Automatic Numbers
  2. Select Contact Number in the left column
  3. Change the Next Contact Number to be Used value to one larger than the Last Contact Number Used value
  4. Click Done 
  5. Create your contact again.