Fixing fill rate issue on Android - best approach?

I have this thread here which is seeking ideas on how to fix my fill rate issues, but I figured I'd ask the question here since I've not attracted any replies there.

From that thread:

I think I've got fill rate issues on some Android devices using a 512x512 atlas drawing 150 tiles (mix of 50 different textures - all in the one atlas) using batching (around 6 or so batches due to indicies count). How would you address this? What are my options?​

There's a lot more specific details in that thread which may help you understand what my issue is and how I came to the conclusion that it's a fill rate issue (which could be wrong).

I'm open to all ideas, so please shoot away if you've got some!