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.

 

Again, the only way this is really safe is if your first Rom was 2.3 based. If I remember right, the item you want to restore is [CONTACTS/CALLS] Contacts Storage 2.3.3

Do you have a backup of that? If so, and the backup was NOT made while on your current Rom (obviously won't include the missing contacts you seek), then you can go this route. If not, you may be out of luck.

In any event, if you're going to restore this (system data), make a nand backup ahead of time in case things don't end well.

 

I had a similar issue, I believe because most of my contacts were phone contacts rather than gmail contacts. I have Verizon's Backup Assistant, but even that didn't seem to sync properly. I exported my contacts FROM Backup
Assistant as a .csv file, and saved it to my desktop. Then I imported the file into my gmail account. I'm saving ALL contacts to gmail which makes Backup Assistant unnecessary, and allows you to easily sync any phone to your gmail account and have immediate access to all of your contacts.