I really don't know how to track this problem to its source, so I was
hoping someone could enlighten me.

The problem illustrated here:
# iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
iptables: Invalid argument

This box is a gentoo running iptables-1.2.8-r1 and linux-2.5.70-mm3.
Config attached.