This looks like a very similar bug to #128 and needs the same fix.
Can the tests not catch stuff like this?
EDIT: Also, the parameter name new_index is slightly confusing since, unlike track indexes, it's not zero-based. libspotify document it with the term new_position which isn't a whole lot clearer but it is a distinction. Maybe a note in the docs to this effect would be nice.
Given that new_position points to a location in the list before any tracks are removed from the list, I'd argue that the index behavior as is is correct and identical with how Python collections works. reorder_tracks() works kind of like insert() of all the tracks on new_index with a following removal from the old index.