I had the same problem and fix it this way:
My app was ~18MB size, and when I see how much memory left free I was shocked – 654KB (on 1GB RAM!). So I just deleted almost all images from project and downloaded them from the internet on first start, and use pics from SD card when needed.
To check total/free memory for your app use:
Runtime.getRuntime().totalMemory();
Runtime.getRuntime().freeMemory();
EDIT: I forgot the main thing – add in your manifest, between application tag, this line:
android:largeHeap="true"