Whenever I try to start Greenshot, I get a message "An instance of Greenshot is already running".

By default, Greenshot is designed to start up automatically with Windows. You can change this either during the installation process or in Greenshot's settings dialog.

If you did not change this option, you do not have to start Greenshot manually, it is already running in the background, just waiting for you to interact with it. You can verify that it is running by identifying the Greenshot icon in your systray. You can start taking screenshot simply by right-clicking the icon or hitting the Print key.