UDP hole punching in python, works locally but not through AWS

I'm trying to implement UDP hole punching so that I can connect 2 clients together that are not in the same network without the need to portforward. I'm using the top answer in this question as my basis and it works if I run the clients and the server on my local machine (both clients get the "hello" response).

Now I've made an AWS instance that is running the server and opened the ports on it so my clients can connect, however when they've received the ip + port for each other they seem to not reach (they get the response "peer: x.x.x.x yyyy", but not the "hello" response). What am I missing in order to make them capable of communicating? even if both clients are on the same machine it still doesn't work, it only gives the correct response when using the local host (127.0.0.1) for both the client and the server.

A "NAT" (Network Address Translation) translates private addresses to a public one when a packet is routed from the internal to the external interface and vice versa in order to allow bi-directional communication.

First a short summary how it works when both clients are behind its own NAT:

• step 1: using a common server both clients must exchange their addresses and agree on port numbers for their future UDP communication: (IP1, port1) <---> (IP2, port2). Note that both IP addresses are the public addresses of the corresponding NAT routers.
• step 2: they both must send a packet to the other side before the channel is usable, the purpose is to create a NAT table entry in each NAT router.
• step 3: peers can now exchange UDP packets. Note that each packet goes through both NAT routers.

Now assume clients A and B are on the same private network behind the same NAT and the common server is elsewhere. In this case:

• step 1: no problem here, but IP1 == IP2 == IP of the public interface of the local NAT router
• step 2: a packet to the other side is a packet addressed to the local NAT router. It will not be forwarded to router's external interface, i.e no NAT necessary, no entry created. The router problably answers with ICMP port unreachable.
• step 3: no chance, as you see