Erasing a bunch of contacts at once?
You can use the Cleanup: remove all contacts app from the appstore to do this. The app costs $0.99



If you want a Mac only solution, you can backup the contacts in your mac's Address Book, connect your phone to your mac and set it to sync only your address book in iTunes. Once it's done syncing (it should now be a clean slate), you can change the sync settings to whatever you wish and then restore your existing contacts from the backup.