I had the same issue and had to solve it myself
Apparently they have more than one starbound server instance on the same physical machine. This means that, everyone that has an instance on there shares the same IP (but different port number)
Your server port is clashing with someone's other instance (or someone's other is clashing with yours). You have to check your assigned port in the admin panel and check if you have the same in your config file set in the 'gameServerPort' field.
Apparently they (Gameservers) are not setting your assigned port when installing the starbound server. They are leaving it as 21025 (the default value). This means that probably more than one instance (owned by different players on the same physical server) is listening to the same port. This makes you connect randomly to one of the instances listening the same port.