This happened to me today when switching from my stock battery to an extended battery I bought from ebay. It sounds like the only choice I have is to factory reset so I will give that a try.
Will backup assistant restore my contacts after a hard reset?
It should. Do you have a mix of contacts between phone storage and Google online? Just make sure to remember to do a good backup assistant session before the reset to be sure you have as much as possible. There still will be the potential for losing some data but should be marginal.