Are you loading any enormous textures? Are your Player Settings all correct? Is your AndroidManifest file set up correctly? An editor.log from the build process might be handy to see what's going into your apk files. I always recommend reviewing that file occasionally to catch any "oops..why the heck is that texture/animation/asset/etc included in the build"
You could be running out of memory on scene loads.