What did you guys wind up doing? I'm having the same problem on my Droid Eris. I did the Clear Data with my Gmail when that was inflating and it didn't kill my Emails, but those are all synced with Gmail - many of my contacts are exclusive to my phone.
EDIT: I did determine (after backing up my Contacts and then clearing the data) that doing so DOES wipe all of your contact data. Those that are synced on Google or thru Exchange would reappear after a sync, but those stored only on the phone would likely not. My only guess is to store them all on a cloud somewhere - Google, Exchange, etc - and that may then work.
UPDATE: Those that are synced on Google or Facebook or Exchange, etc WILL reappear on your phone. My phone Contacts Storage went from 6.39MB to 1.71MB when I did this. Any contacts that were on my phone only were erased, but it was only a few that weren't synced somehow. If you do choose to do this then I highly recommend you back them up using one of the backup apps on the Market. I use Titanium, which is an awesome app, but you have to be rooted to use it.