А знаю из-за чего это =) сам первый раз был удивлен.
У вас на телефоне стоит это же приложение, но подписанное отладочным ключем (или любым другим), поэтому, когда вы станавливаете это же приложение из маркета, подписанное настоящим ключем, установка не проходит с такой вот ошибкой.
Удалите со смартфона отладочную версию вашего приложения и установка из маркета пройдет гладко.