I had a similar problem and the only way I found to delete the contacts was to delete them from Gmail and then resync with gmail. So with no contacts in gmail when you sync the ones on your phone get deleted. It took a few tries at syncing as it seemed to only delete a portion of them at a time. Of course, before you delete the contacts from gmail you would download them to a csv file using the export option in gmail. Then when the ones from your phone are gone, import the contacts back into gmail. Pain in the butt...I know, but it works!
Thanks for your suggestion, it worked great.