I'm with the iPhone Backup Extractor team, I must point out that the free version of the software will only extract four records of each category (contacts, sms, photos, etc.) when used in Simple Mode. The limitation in extraction might be why you only found four contacts in your backup when using it.
The application will show you exactly how many contacts were detected in the iTunes backup under "Available data", in the "Contacts" section (it's the number shown in blue).
Also, you can see how many backups you have and change from the dropdown menu which backup you wish to extract from. If there really are just four contacts in that backup, do try to see if there are any other previous backups which contain the data you are looking for.
Even when backups are corrupt or damaged in some way, if the data exists and has not been overwritten, it is possible to recover it. I would suggest contacting the iPhone Backup Extractor customer support team (firstname.lastname@example.org) if all else fails - we have four years experience working with iTunes backups and we have helped many users recover their data, perhaps we can do the same for you.