システムアプリなど.apkとは別に.odexというファイルがある場合、
一度.odexを分解してapkの中に入れないといけません。

まず.odexをsmaliに分解したあとclasses.dexにします。
このサイトからsmaliとbacksmali、smali-1.4.2.jarとbacksmali-1.4.2.jar をダウンロードしてください。
(ベータ版ですが2.0のほうでもいいです)

Cドライブ直下にフォルダを作り(例:deodex)、
ダウンロードした四つのファイルをそこに入れてください。
後で操作しやすくするため、.jarのほうはsmali.jar、backsmali.jarというようにしてください。

そのフォルダでShift+右クリックでコマンドプロンプトを開くなどして

adb pull /system/framework

と入力してEnterキーを押してください。
これでsmaliなど四ファイルのあるフォルダに/system/frameworkのapkやjarがコピーされます。

deodexしたいapkとodexを入れるフォルダ(例:old)を作り、そこにapkとodexをコピーします。
smali、backsmaliのあるフォルダ(deodex)でコマンドプロンプトを開き、

java -jar baksmali.jar -x oldXXXXX.odex -o test

と入力してEnterキーを押してください。(XXXXX.はoldフォルダに入れたodexの名前にしてください)
これでtestフォルダが自動生成され、その中にsmaliファイルがでてきます。
ここでsmaliの編集をしてください。

次に

java -jar smali.jar test -o modefied_classes.dex

と入力してEnterキーを押してください。
これでtestフォルダ内のファイルがmodefied_classes.dexに変換されます。

このmodefied_classes.dexをデスクトップなどにコピーし、classes.dexに名前を変えて、
元のapkを7zipなどで開き、無圧縮でclasses.dexを入れてください。

ここまでの操作でdeodexが完了しました。
odexを再生成しない場合、端末内の元々あったXXXXX.odexを
削除した上でdeodexしたものをコピーしてください。
ちなみにxUltimateというツールを使えばここまで自動でしてくれます。

一部deodexすると動作がおかしくなる場合があるので、
その場合はdeodexしたapkから再度odexを生成するようにします。
(本当はdeodexのままで解決できそうですがそこまでの知識がないもので…)

まずこのページでdexopt-wrapperをダウンロードしてください。

deodexしたapk(もしくはjar)とdexopt-wrapperを同じフォルダに置き、コマンドプロンプトを開いて

adb push XXXXX.apk /data/local/tmp/
adb push dexopt-wrapper /data/local/tmp/
adb shell chmod 755 /data/local/tmp/dexopt-wrapper
adb shell
cd /data/local/tmp
./dexopt-wrapper XXXXX.apk XXXXX..odex
busybox dd if=/system/framework/XXXXX..odex of=XXXXX..odex bs=1 count=20 skip=52 seek=52 conv=notrunc

というふうに順番に実行してください。
最後のbusybox dd if=は端末内に元々あったXXXXX..odexのパスにしてください。

これで/data/local/tmp/にXXXXX..odexが生成されます。
後はこのodexを端末内のodexに上書きして終了です。