openssh-server not completely configured
I was fighting a lack of ssh access on my internal network too on a recent install. I suspected the firewall too but disabling it or allowing port 22 didn't help. In the end: dpkg-reconfigure openssh-server re-generated the host keys and now I have ssh access, with firewall enabled, maybe the keys aren't getting generated correctly on install. I haven't tried external access yet.
-Coley.