I'm running Kubuntu and have a bit of a problem with network.
Everything else works, but apt-get fails to connect. Any FTP downloads aren't working either.
My router is D-Link G604T with NAT enabled.
Also a problem occured during installation, but I got rid of it, when I unplugged the ethernet cable for the installation. With the cable connected it stuck, however, to something related to apt configuration and network.

First thing I would do is see if you can connect to the internet, then if it is a localized problem with ftp check to make sure your router isn't blocking outbound ftp. Then see if you can even get a clean route, just try and telnet to port 21 on the servers listed in your apt-sources.list.

The network is working fine. Even FTP works good on Windows. On Kubuntu the only problems seem to be FTP and especially apt-get.
I am really a newbie, and I actually don't know how to use Telnet...

Hehe no prob.
I have not used kubuntu but since it is derived from debian I will give you the steps I would check on a debian box.
First I would do a:
$ cat /etc/apt/sources.list
you will see lines like the following:
deb http://mirrors.kernel.org/debian/ testing main contrib non-free
deb-src http://mirrors.kernel.org/debian/ testing main

deb http://security.debian.org/ testing/updates main
yours will most likely be ftp:// so strip out everything except the hostname and do the following:
$ telnet mirrors.kernel.org 21
if it connects then it will say "welcome to <hostname>" or the version of ftpd software they are using.
if it connects hit Ctrl + ] and enter to quit then type in quit.
if this works then you are able to connect on port 21 then please dump the error you are getting with apt

Ok, I tried that, nothing happened, it just said "Trying 1.0.0.0..." and nothing else...
I've opened up the port 21 in my router config, so that _should_ not be the matter..
Any more ideas?

Yep, please post your /etc/apt/sources.list.

## The following lines pertain to supported packages:
deb http://archive.ubuntu.com/ubuntu hoary main restricted
deb-src http://archive.ubuntu.com/ubuntu hoary main restricted

## The following lines pertain to security updates:
deb http://security.ubuntu.com/ubuntu hoary-security main restricted
deb-src http://security.ubuntu.com/ubuntu hoary-security main restricted

## Uncomment after release to continue getting updates:
deb http://archive.ubuntu.com/ubuntu hoary-updates main restricted

## IMPORTANT:
## Software from the following repositories are ENTIRELY UNSUPPORTED by
## the Ubuntu team, and may not be under a free licence. This means that
## software in these repositories WILL NOT receive any review or updates
## from the Ubuntu security team either. These packages are provided as a
## service to our users and nothing more.

## Uncomment the following two lines to add software from the 'universe' and
## 'multiverse' repositories:
deb http://archive.ubuntu.com/ubuntu hoary universe multiverse
deb-src http://archive.ubuntu.com/ubuntu hoary universe multiverse

## Uncomment the following line to add Java software:
# deb http://jrfonseca.dyndns.org/debian/ ./

## backports and extras
#deb http://backports.ubuntuforums.org/backports hoary-extras main universe multiverse restricted
#deb http://backports.ubuntuforums.org/backports hoary-backports main universe multiverse restricted

## mplayer
#deb ftp://ftp.nerim.net/debian-marillat/ stable main
#deb ftp://ftp.nerim.net/debian-marillat/ unstable main
#deb ftp://ftp.nerim.net/debian-marillat/ testing main

## great KDE-software like amaroK, Qt-GTK-engine, OpenOffice.org-Qt
#deb http://archive.kalyxo.org/ staging main
## mirror of above
#deb http://kalyxo-archive.mornfall.net/ staging main

## kubuntu digikam, kipi-plugins
deb http://www.mpe.mpg.de/~ach/kubuntu/hoary ./
deb-src http://www.mpe.mpg.de/~ach/kubuntu/hoary ./

## suomenkielinen oikoluku / Finnish non-free spelling software "Soikko"
#deb http://elonen.iki.fi/code/unofficial-debs/ ./

## Official Debian sources
#deb ftp://ftp.fi.debian.org/debian/ sarge main contrib non-free
#deb ftp://ftp.fi.debian.org/debian/ unstable main contrib non-free

## Horde
#deb http://debian.opal.dhs.org unstable main contrib non-free
#deb http://debian.opal.dhs.org sarge main contrib non-free

What is the error that apt gives you when you try to connect? Everything looks pretty good in your sources.list

With all the servers in the list it just gives
"Err http://security.ubuntu.com hoary-security Release.gpg
Could not connect to security.ubuntu.com:80 (1.0.0.0), connection timed out"
(seems the problem wasn't with the port since it's 80, not 21..?)

I have the same router, your linux its ok, the problem is the router + linux, internet only works a few time in linux, and it works perfectly with windows, strange for a router with a linux as firmware.

you can know more about the router here:

http://www.seattlewireless.net/index.cgi/DlinkDslG604t

And here you have modified firmwares:

http://mcmcc.bat.ru/dlinkt/?C=M;O=A