I might try ejecta again and see, I haven't used it in a while, mostly because it was iAd only. For this app, I might actually use iAds so it might work out.
However I am getting far with optimizing. It's good to note that you do need a 2 pixel buffer for the image sheets. I had all of my graphics set to a power of 2 (256, 512, etc). This actually causes more sprite sheets than needed. If I reduce size of all of them by 2 pixels, I can squeeze more on each sheet, creating less total sheets.