Is the routing the exact same to the dot? If your IP changed you're likely going down different circuits/ports while going through essentially the same route. Try looking at the beginning of the names in the traces, they sometimes clue into this.
Also, might want to consider checking reverse traceroutes/pings to see what the return path is like too.
·