If you have many contacts to delete, search the App Store for an app called My Contacts Backup (free, and available in the US App Store, I don't know about other countries). One of it's options (within the app under the settings "gear" icon, then scroll down to the bottom) is to Remove All Contacts...this is exactly what it does. In one shot. Be ready because you will lose all of them. Before doing so, you should make a backup of the contacts and archive it, email it to yourself. This is the main feature of the app, to archive...not to just remove contacts. None of your other data will be touched.