Can't lock session

When trying to lock the session I get:
"Could not execute command: gnome-screensaver-command --lock. Verify that this is a valid command"

Installing the gnome-screensaver package brings back the usual behavior (screen locked, unlock dialog chown when keyboard/mouse activity detected).