I ran into the same problem but was able to fix it with Time Machine. The contacts app has special support for Time Machine (you can slide through time and don't have to go to the Finder) and I could restore all my contacts from a few weeks ago.