So I saved all my contacts by selecting the google account instead of saving on the phone.
But I removed the accounts from the phone, and when i added back the accounts to the phone, i could not find most of the new numbers..
Please help!
As MemCtrl mentioned, go to http://contacts.google.com and see if your contacts (with the new numbers) are there. If not, you can restore them using "Restore contacts..." option (hit the "More..." button to see it), provided they weren't deleted more than 30 days ago.
Go to contacts.google.com - see if you can find them there. If not, then I'm afraid you're out of luck.
Settings -> Accounts -> Google -> <your account> -> Menu -> Sync now
.