Why does MySQL flag a duplicate key where none exists?
I tried running your code in MySQL 5.7.12 for MacOS. I can't seem to duplicate this, but I found something interesting.

SQL-Fiddle has MySQL 5.7.17. You got the error in MySQL 5.7.13. Was anything with regard to dropping and adding a secondary index fixed between those versions ? I believe it was. Please note the Release Notes for 5.7.14, bulletpoint 21 under the subheading Bugs Fixed:


  InnoDB: An assertion was raised during rollback of an ALTER TABLE operation that dropped and added a secondary index. (Bug #22005726)


Question: What is a secondary index ? According to the MySQL Documentation for Clustered and Secondary Indexes right under the heading How Secondary Indexes Relate to the Clustered Index:


  All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.


This show that a UNIQUE INDEX is just a secondary index. A secondary index would have a copy of the PRIMARY KEY attached to every index entry. 

My assertion is that a bug was introduced in 5.7.13 that did not exist in 5.7.12 when it comes to dropping and creating an index on the same column(s) at the same time. 

Look back at your ALTER TABLE command

mysql&gt; ALTER TABLE my_table
        DROP INDEX `idx_new_id`,
        ADD UNIQUE INDEX `idx_new_id` USING BTREE (`new_id `);


You dropped an index with a specific index name (idx_new_id) and with a specific column list (just one column, new_id) and then said add a new index with the same name and the same column list but make it the index UNIQUE. The net effect is that the index was never really dropped and the UNIQUE attribute was simply attached to the already existing non-unique index. Then, under the hood, mysqld attempted to load data into the table which is already populated and an index that's still populated, thus creating a duplicate key error. Please note I am only asserting this. I would have to look at source code for 5.7.13 to see if this is indeed occurring.

Notwithstanding, 5.7.12 and 5.7.14 cannot reproduce this problem. This indicates that this strange condition was addressed when making 5.7.14.

In light of all my conjecture, here are my suggestions:

SUGGESTIONS

SUGGESTION #1 : Upgrade to 5.7.14 or above

SUGGESTION #2 : Change the ALTER TABLE to use a different index name

mysql&gt; ALTER TABLE my_table
       DROP INDEX `idx_new_id`,
       ADD UNIQUE INDEX `uniq_idx_new_id` USING BTREE (`new_id`);


SUGGESTION #3 : Do 2 ALTER TABLE commands

mysql&gt; ALTER TABLE my_table DROP INDEX `idx_new_id`;
mysql&gt; ALTER TABLE my_table ADD UNIQUE INDEX `uniq_idx_new_id` USING BTREE (`new_id`);


GIVE IT A TRY !!!