What are you looking for the app to do? Anyway, search the market (or appbrain) for Better Contacts. It's not really a replacement, because it won't act as the default contacts app, but it offers some nice features.
You might also want to check out Dialer One or aTakePhone, which are dialer replacements, but let you search your contacts database.