I hope someone can help me, but first of all : "TA Spring is really great"

This is my current situation:
On my PC (Ubuntu 7.10):
- Spring 0.76b1 (repository-install)
- TASServer.jar (LAN-Mode)
On my friend's pc (Windows XP Home):
- Spring 0.76b1 (Windows-Installer)
We are not in a LAN environment, so we both enabled port forwarding on our routers (8000-8500 TCP & UDP).
We can both connect to the LobbyServer where it all seems to work allright. (chat, hosting games,... is working)
The problem occurs when we try to start a battle. The host can connect as used while the client only get's "Connecting to server". After a while he is kicked back to the lobby.
Singleplayer-games work for both of us.
Has someone already tried something like this and got it working?