This same problem can affect new 1:1 and Server NAT configurations.
Cause. This is typically caused by the router outside of your m0n0wall having the MAC address of your previous firewall still in its ARP table. Cisco routers, for example, will cache this for four hours by default. Many other routers are similar.
Clear the ARP cache on your router. If you don't have access to the command interface of the router, or don't know how to clear the ARP cache, power cycling the router should achieve the same result.
Alternatively, you could fill in the MAC address of the WAN interface of your previous firewall in m0n0wall's WAN interface screen.