Joao: you can configure XScreenSaver to show a “Switch User” button in it’s password dialog (which calls gdmflexiserver when run). This lets you start a new X session after the screen has locked. This feature is turned on in Ubuntu if you want to try it out.
Of course, this is not a full solution, since it doesn’t help you switch to an existing session (you’d need to guess the correct Ctrl+Alt+Fn combo). There is code in gnome-screensaver to support this though, giving you a list of sessions you can switch to.