So for a few months I decided to just re-route game data to a server with a static IP address because I could not get peer-to-peer working. Someone said it is 100% possible to do, so anyone that has a multiplayer game on android hook me up with some code or something. This is all with UDP.

I have: a static IP for a matchmaking server (in c++)
Right now I can send both clients data to the server, and the server will route those updates back to the other players. So all the game logic works.

This means I know the IP's of the two players phones, and I can send stuff over the network. However, I have a feeling that packets are getting dropped because when the players try to send to each other, without routing everything to the server, they come from a new address that the NAT does not know of.

My test:
If I run a 2nd program on the server that is bound to a new port, the phone will not receive ANY data from that new port so:
Client sends to server @ 111.1.1.2:8004
Server sends to client from 111.1.1.2:8004
Client gets a response.

A new program sends to client from 111.1.1.2:9004 << will not make it to the phone.
111.1.1.2:8004 will still make it to phone.

This is doesn't work while I'm connected to my wifi either. So I don't know why my router would be dropping those packets.

That's pretty normal for NAT gateways, and also for certain firewall configurations even if they don't actually translate the addresses. What you need is to use the first server as a NAT introducer for NAT punch-through.
I wrote a chapter in Game Programming Gems 5 about this. An earlier web article about the same thing is here:
http://www.mindcontrol.org/~hplus/nat-punch.html

I have read that and I have written a c++ game on windows with networking before, so I assume something about java sockets I am missing or something with android. I already have the introducer, these 2 players know their IP's, they use that same socket to send data to those IPs.

I read an hour ago that a udp sockets should be able to break a firewall as long as the socket did send a request to a specific IP, it should be able to receive data back from that specific IP and that throughout its lifetime it can continually switch who it sends to and that should update who it is allowed to receive from.

Other than that I'm about to strip down to a basic application and see what happens if it isn't something completely stupid.

I have read that

I read an hour ago that a udp sockets should be able to break a firewall as long as the socket did send a request to a specific IP
[/quote]

Given that that's the whole gist of NAT punch-through, I wonder how you got the punch-through to work before?

Well I guess my new router/modem or some other router/modem could be using symmetric NAT. But I don't know how you are going to be able to get peer to peer from that unless you can do some port prediction.

I think it may somehow be using a specific type of symmetric NAT and will verify.

FYI, for my router/modem I can't match-make players on the same machine. They will not work unless I send to 192.168.0.1:player_port, if I send to my routers global IP, then they will not receive each others messages.

The new system I'm doing is hole-punching that way it covers more options of NAT's
Open 3 ports:
A - port 12000
B - port 12001
C - port 12002

A -> contact server , server sees NAT port 32490
B-> contact server , server seets NAT port 32495

Server knows now that port C must bee 32500 (each new port is the previous port + 5).

So when matchmaking, the server tells each player what the port C of both players should be, by sending a reply to each players A port. Since those ports C have never sent anything, their first request/send will be to each others port C and therefore you break through.