Router firmware upgrade, then PuTTY warnings?

I run an SSH tunnel through my Linode from home. Tonight I upgraded the firmware on my router, and immediately afterward when I went to connect to my Linode with PuTTY, I got a warning that my key fingerprint had changed. From Android, ConnectBot says this might be a man-in-the-middle attack (similar warning).

I'm guessing (emphasis on guessing) that this relates somehow to my router firmware upgrade, just given the timing, but on the other hand, why would that have any effect on the Linode's RSA key fingerprint? It doesn't make sense to me other than the fact that the router does sit "in the middle" of this connection. When I connect to my Linode using a device off my LAN (my smartphone), I get no warning, and the key as reported by "ssh localhost" is different than the one reported when I connect from my LAN.

In short, how worried should I be? I suppose I have some reading to do before I understand this, but I'm hoping someone can shed some insight.