基本中の基本のことだが、パッケージの階層を手動でリファクタリングした詰まったのでメモっとく。
環境はAndroid Studio 1.2

以下エラーメッセージ

pkg: /data/local/tmp/package_name
Failure [INSTALL_FAILED_INVALID_APK]

NG例

以下のように、Javaフォルダ以下が１階層の構成だとダメ。

エラーにとなるフォルダ構成

src
├── AndroidManifest.xml
└──  java
    └── example
       └── Hoge.java

エラーとなるAndroidManifest.xml

.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="example" >

...

OK例

以下のように、フォルダ階層を一つ以上増やしてやればOK。

修正後のフォルダ構成

src
├── AndroidManifest.xml
└──  java
    └── example
        └── com
            └── Hoge.java

修正後のAndroidManifest.xml

.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="example.com" >

...

package=〜 で指定するパッケージは、最低でも２階層必要らしい。
ちなみにAndroid Studioのプロジェクト作成時にパッケージを１階層にしようとすると、

.java

Invalid package name: The package must have at least one '.' separator

という警告が出てそもそもプロジェクトを作成できない。