Solved it: I had ipmasq installed on the CLIENT, which was apparently setting up some iptables that interfered with the new default route.
Presumably firewall-easy would now work on the server, but I think I'll stick with firehol anyway. It does seem to be quite a nice tool.
