I was able to connect to the STK600 using AVR Studio on a Windows machine to set the voltage. After that, avrdude seemed to work for a time, but after typing a command wrong, it went back to giving me this error every time.
I'm using the avrdude 5.10 which is available through Ubuntu's package manager.
In case it helps, here's the verbose output of the following command.
> avrdude -c stk600 -p atmega2560 -P usb -v
avrdude: Version 5.10, compiled on Mar 23 2010 at 15:03:00
Copyright (c) 2007-2009 Joerg Wunsch
System wide configuration file is "/etc/avrdude.conf"
User configuration file is "/home/hayden/.avrduderc"
User configuration file does not exist or is not a regular file, skipping
Using Port : usb
Using Programmer : stk600
avrdude: usbdev_open(): Found STK600, serno: 0045E550839C
AVR Part : ATMEGA2560
Chip Erase delay : 9000 us
PAGEL : PD7
BS2 : PA0
RESET disposition : dedicated
RETRY pulse : SCK
serial program mode : yes
parallel program mode : yes
Timeout : 200
StabDelay : 100
CmdexeDelay : 25
SyncLoops : 32
ByteDelay : 0
PollIndex : 3
PollValue : 0x53
Memory Detail :
Block Poll Page Polled
Memory Type Mode Delay Size Indx Paged Size Size #Pages MinW MaxW ReadBack
----------- ---- ----- ----- ---- ------ ------ ---- ------ ----- ----- ---------
eeprom 65 10 8 0 no 4096 8 0 9000 9000 0x00 0x00
flash 65 10 256 0 yes 262144 256 1024 4500 4500 0x00 0x00
lfuse 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
hfuse 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
efuse 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
lock 0 0 0 0 no 1 0 0 9000 9000 0x00 0x00
calibration 0 0 0 0 no 1 0 0 0 0 0x00 0x00
signature 0 0 0 0 no 3 0 0 0 0 0x00 0x00
Programmer Type : STK600
Description : Atmel STK600
Programmer Model: STK600
Hardware Version: 3
Firmware Version Master : 2.06
Firmware Version Slave 1: 2.01
Firmware Version Slave 2: 2.00
Routing card : Not present
Socket card : STK600-ATMEGA2560
RC_ID table rev : 26
EC_ID table rev : 1
Vtarget : 5.0 V
Varef 0 : 4.99 V
Varef 1 : 4.99 V
SCK period : 5.00 us
Oscillator : 199.976 kHz
avrdude: stk500v2_program_enable(): bad STK600 connection status: Target not detected (0x00)
avrdude: initialization failed, rc=-1
Double check connections and try again, or use -F to override
this check.
avrdude done. Thank you.