i have the same issue as well. i am however trying to connect to a dedicated server that others have no issue connecting to. i do go through a router with NAT, and that is necessary.
it takes at least 3 times to get a connection, sometimes i can never connect with even 7 tries. get connection failed message. if i do by some miracle get into the game, it takes about a minute before the connection gets gradually worse; broken yellow chain, broken red chain, red chain with the messages 'no message to 10 seconds', etc. eventially i just have to drop.
anyone have any ideas? all the udp ports are allowed to the dedicated server and my game machine is in a DMZ.