This might be completely obvious, but if they are on different networks, you may just need a hole in the firewall on port 5432 too.

Glad to see you've gone with Postgres. I started with it a couple of weeks ago. Seems to be on the up and up, esp. when v7.1 hits the streets.