It seems that Lion is not compatible with Time Capsule, or at least not fully compatible.
This way I got it to work:
From the menu, choose Utilities > Terminal..
In the terminal, type the following commands:
Note: leave out the "-bash-3.2#" part, it will be printed automatically for you
Note2: replace the stuff between [] with information that applies to your situation
-bash-3.2# mkdir /Volumes/tc
-bash-3.2# mount_afp -i afp://[ip-of-timecapsule]/[username] /Volumes/tc
User: [usename]
Pass: [password]
-bash-3.2# hdiutil mount /Volumes/tc/[username].sparsebundle
Now go back to the recovery assistant and there will be an extra disk called "Time Machine Backups".
Select it as a backup drive and continue the process as normal.
