Conforme a série de respostas em INSTALL_FAILED_UPDATE_INCOMPATIBLE when I try to install compiled .apk on device
Esta mensagem quer dizer que o aplicativo já esta instalado:
Failure [INSTALL_FAILED_UPDATE_INCOMPATIBLE]
Isto pode ocorrer por talvez ter instalado o aplicativo de outra maneira, ou instalou via root ou via playstore, você pode tentar desinstalar via adb:
adb uninstall <nome do pacote>
Ou então você pode desinstalar pelo próprio celular, vá até Settings > Apps e selecione seu App e clique em Uninstall
Versões mais recentes do Android basta arrastar o App e no topo da tela aparece o Uninstall (ou Desinstalar):
Nota: Se aparecer apenas o Remove significa que não é possível desinstalar
Teria alguma maneira de resolver este problema sem perder os dados existentes?
Existem algumas, ainda sim se o problema ocorre a todos momento você deveria checar o que esta ocorrendo, provavelmente estava tentando instalar o app por meios diferentes, ou o teu ADT esta desatualizado.
Nota: Se aparecer apenas o Remove significa que não é possível desinstalar
Clique em Setting
Vá até Back up & sync:
Ligue o backup clicando em ON (se estiver off):
Clique em Backup All
Ou então pode usar um aplicativo como: