Para que funcione no seu roteador, você precisa adicionar especificamente o endereço da sua interface externa (voltada para a Internet pública) à regra.
Caso contrário, você está enviando o pacote para a Internet com seu endereço IP privado como fonte.
Pode ser possível que seu kernel específico, a versão do netfilter, se comporte de maneira diferente. Você pode verificar o que está acontecendo com o tcpdump.
iptables -t nat -I POSTROUTING 1 -p udp --sport 123 -j SNAT --to-source {PUBLIC_IP}:12512
Então (assumindo que eth1 é sua interface de internet):
tcpdump -ni eth1 port 123
Isto é o que eu tenho em /etc/firewall.user no OpenWRT:
P_IP='/sbin/ifconfig eth1 | awk '/inet addr/{print substr($2,6)}''
/usr/sbin/iptables -t nat -I postrouting_rule -p udp -o eth1 --sport 123 --dport 123 -j SNAT --to $P_IP:12300
Não se esqueça de limpar as tabelas do conntrack depois de fazer alterações no firewall, se quiser ver os resultados imediatamente, no OpenWRT:
echo f > /proc/net/nf_conntrack
Caso contrário, pode ser realmente confuso o que está acontecendo.