TIme Machine IP Change Loses Backup History
The new router (the hardware did change) is obviously using one of the default 192.* ranges instead of the 10.* range the old router was using. Your iMac and NAS picked up an address in the new IP range, (that's why the iMac could 'see' the NAS,) but because the IP in the NAT changed, Time Machine failed.

When you change routers in the future, you should make sure the iMac and NAS pick up an IP in the same range as the old router so there is no mismatch.