Based off of what I found in a google help forums, try these steps.
Open up your inbox, go to menu->tools->manage folders, expand the one labeled gmail or google mail, select the folder named All Mail,and you should be able to delete it from there.
I've altered the original to apply for how I needed to go using my phone (I'm having other syncing issues at the moment so I can't test how this works.) The original answer is located here.
http://www.google.com/support/forum/p/Google+Mobile/thread?tid=0273759a103c07f0&hl=en
Hopefully this will work for you.