Since adb is installed and seems to be working, Eclipse is probably having a problem finding or starting adb. First, check that Eclipse has the right location set for the sdk (Window->Preferences->Android or slightly different on Mac). I think it should based on the error message. Then, if you still can't run the app from Eclipse, try starting adb from the command line with adb start-server
.
EDIT: If the app still won't run after doing the above, make sure adb is able to find your device or emulator. Start the emulator or connect your device, then run adb devices
from the terminal. If your device or emulator is not listed, adb can't connect to it. If it is an actual device, make sure USB debugging under developer options in the device settings is enabled.