I'm NAT'ed, but I thought it should be able to handle that - most networks that needs VPN are like that. I'm assuming that the way hamachi works is that each client is connected to an external hamachi server, then when two clients connect they use the info on the common server to negotiate an UDP tunnel directly between them. Or something like that. I'm guessing that these UDP packets are somehow being blocked in my firewall, although Skype (which does something similar) works fine on my nets, as far as I can tell.
So, I'm going to try hamachi between some other networks. I was hoping I could use it here though.