Following up on this entry — it seems that my “hindsight” section was correct.
The simplest solution was just to put everything on the Dlink and setup double port forwarding. That is, I setup the Linksys to forward incoming port 22 to the IP address of the Dlink. Then I setup the Dlink to forward port 22 to the IP address of my linux box. This seems to work just fine (as it should) — I can ssh into my linux box from the outside world.
And now all my machines are back on one subnet, so I don’t have to deal with printing and file sharing woes.