Why would an iptables rule for ANY proto only allow ICMP traffic?

Basically, I have a Linux box (Ubuntu Focal) configured as a gateway:

sysctl net.ipv4.ip_forward = 1   #Enable ipv4 forwarding
iptables -t nat -A POSTROUTING -o ens160 -s 192.168.1.0/24 -j MASQUERADE  #NAT 192.168.1.x to internet behind interface ens160

Having done this, I can ping successfully:

And I see the hit count increase on the masquerade rule (from 1 to 2 in this example):

The rule is duplicated in the previous picture because of all the stuff I was trying at the time I took the screenshot, but its not really significant in this example I don't think.

So I can ping 8.8.8.8 just fine, but if I try to do something else, like for example a DNS lookup like

dig @8.8.8.8 www.google.com

This fails and the hit count on the rule does not increase.

I also tried using telnet to open an HTTP (not HTTPS) website by IP address (not name), and this also fails, with the hit count not increasing.

I'm really at a loss for what could be causing this, since this procedure normally works and the rule itself is saying that it applies to all protocols, not just ICMP, but it seems to be the case that I can ping anything by IP address, but DNS lookups (UDP) and TCP connections are failing because the gateway is not sending them out.

I did a tcpdump as well and you can see the packets coming in as 192.168.1.x, and in the case of ICMP you also see the NATted packets leaving, but for UDP/TCP you don't see anything leaving.

What might be the issue here?

Edit: Adding some more info as per some of the feedback from comments

The filter and raw tables don't seem to have anything in there. I'm not sure if I'm using the right command to check these, but I think so:

iptables-save -c doesn't show anything besides what I expect either. (There are some dupes of the rule I added due to repeated trial & error, but I don't think these have any impact):

sudo iptables-save -c
# Generated by iptables-save v1.8.4 on Tue May  2 18:59:25 2023
*raw
:PREROUTING ACCEPT [290378:642993821]
:OUTPUT ACCEPT [26621:1727859]
COMMIT
# Completed on Tue May  2 18:59:25 2023
# Generated by iptables-save v1.8.4 on Tue May  2 18:59:25 2023
*filter
:INPUT ACCEPT [290051:642964315]
:FORWARD ACCEPT [140:11615]
:OUTPUT ACCEPT [26631:1728900]
COMMIT
# Completed on Tue May  2 18:59:25 2023
# Generated by iptables-save v1.8.4 on Tue May  2 18:59:25 2023
*nat
:PREROUTING ACCEPT [72935:11925313]
:INPUT ACCEPT [72704:11903229]
:OUTPUT ACCEPT [1643:146886]
:POSTROUTING ACCEPT [1643:146886]
[11:924] -A POSTROUTING -s 192.168.1.0/24 -o ens160 -j MASQUERADE
[0:0] -A POSTROUTING -s 192.168.1.0/24 -o ens160 -j MASQUERADE
[0:0] -A POSTROUTING -s 192.168.1.0/32 -o ens160 -j MASQUERADE
COMMIT
# Completed on Tue May  2 18:59:25 2023

I myself am not really able to get any additional insights from this output, any suggestions?

Edit 2: Adding some more info as per the comments

I don't believe NFtables was ever installed, but nft list chains doesn't give anything, and the routes for icmp and udp seem to be the same:

It's really quite strange since DNS requests originating from within the gateway VM itself (the system DNS isn't set to 8.8.8.8) seem to get SNATted and go out no problem, and even get a response, but for whatever reason inbound DNS requests from the private LAN just die on arrival: