K8S Cluster Pod Issue – Pod Can’t Resolve Service Name if on Different Node from CoreDNS Pod

I created a k8s Cluster v1.26.0 with kubeadm and I am using Calico as CNI. I deploy calico with the helm chart and I followed the steps by the Calico official page and chart.

The container engine is containerd.
The nodes Node are Centos 8 and we configured iptables in firewalld as this thread suggested:
Link

The problem is that when we are trying to run nslookup with a dnsutils pod. It does not work. I get a timeout error when the pod tries to reach kube-dns.kube-system. If the dnsutils pod is scheduled on the node that runs coredns, we can nslookup the service normally. We can ping the pod ip directly but when we try {Service Name}.{Namespace} this doesn't work on any pod that is schedule on a different node than the node running coredns.

We checked all firewall rules required by Calico and all of the required port are open and accessible. We checked kube-proxy with --v=4 and it lists all service names and cluster ip in it.
We checked iptables and it seems to have rules like Debug Service page from the official Kubernetes site.

I have struggled on this for 4-5 days now and I really need some suggestions to debug or an understand of that is really going on in our cluster.