It is possible to make a VPN connection on Linux. This works Shrew Soft VPN client v2.1.5. Ubuntu 9.10 has still v2.1.4, which does not work for the Fritz!Box VPN.
The Shrew Soft VPN client v2.1.5 will be available in Ubuntu 10.04 (Lucid)
Make under Linux
Download the VPN client from: shrew.net/download/ike
Read the README.txt about how to compile and install the client.
Configuring the Shrew Soft VPN client
That is exactly the same as the Windows version of the VPN client, see VPN via Fritz!Box on Windows for instructions.
This article belongs to the Fritz!Box VPN guide. The other articles in the guide are: