While I have not done this myself (I do not have an STK500), it should definitely be possible.
Let me ask a couple of things to point you in the right direction.
– Was this a preprogrammed ATmega644A (e.g., for the Alpha Clock Five)? If so, the fuse bits are set to require an external crystal oscillator. Make sure that you’ve provided one, or are programming it on a board that provides one.
– Are you using the latest version of Atmel Studio? The ‘644A is a relatively new device, not supported by all older versions.
– Is it possible that your STK500 needs a firmware update? (I’m not sure that it does, however, we have needed to run firmware updates on our Atmel AVRISPmkII devices.)