As you have determined, you will not be able to restore the AutoNumber Property. First, you MUST make a copy of the database, so that if anything else goes wrong, you can start over, and then you will have to consider taking the following steps.
Eliminate any gaps in the existing AutoNumbers
Open up the table and insert blank records as placeholders for any missing numbers. Mark these records in a unique manner, so that they will be easier to find and remove later.
Verify that the old Autonumber Sequence has no gaps.
Create a column for the new AutoNumbers
Add the column in Design Mode.
Opening the Table in DataSheet Mode to show the new AutoNumber Values.
Verify that the New Values match the old ones. If they do not, you will need to remove the new AutoNumber Field and redo Step 1 until they match.
Established relationships should remain unless original column has been removed.
Identify the affected relationships, break the existing links, and establish links to the new column
Cleanup the data
Remove any placeholder records that were inserted.
Rename previous PrimaryID column to save the values
Do not remove this column until you are sure the operation is completed successfully
Rename the New AutoNum Column to have the same name as the previous PrimaryID column.
Verify that the table has been updated successfully.