My first guess is to make sure both UDP and TCP ports on all of the right numbers are open in the router. I believe that Avorion will fallback to pure TCP over the game port, but the game is probably trying other options and eventually falling back to that. I have TCP and UDP open to 27000, 27003, 27020, & 27021 for reference. I'm pretty sure those don't all have to be both TCP and UDP, but I know in my case that the extra protocols aren't going to hurt.