Maybe they weren't set up as Google contacts but instead were "phone" contacts. If you have a nandroid of a previous setup that would have the lost contacts, first nand Nils, then restore back to previous Rom. Convert any phone contacts to Google variety, then restore back to Nils and nothing left to do.
If your previous Rom and this one happened to both be sense or much more ideally Gingersense, you may be able to restore them via Titanium if you use it. Safer route is the first option IMO.