There are many reports about access violation errors. These are caused by the UAC function in Vista. This function prohibits creation and modification of files inside the "Program Files" folder, even if you are Administrator on your machine.
A workaround is to install Sokoban in a folder outside "Program Files". To reinstall, take the following steps:
1) Uninstall Sokoban.
2) Reinstall in a new folder, for example "C:\Games\Sokoban 3".
3) Manually copy files from the old to the new installation. All files in the Scores folder, all files in the OwnLevels folder. From the "Sokoban 3" folder, copy all files named Player_N.sav and Current.sfl