I had exactly the same problem when i deleted my mobileme account. Where everything syncs with Mac it puts your contacts and all your dates from your calendar into the same folder, so when you delete the account you lose all of that information.
I got round this on my Mac by opening the address book (if your iPhone was regularly synced all/most of your contacts should be in there) and going to edit, select all and then exported them to documents. It exported all my contacts to one V Card. After this i made sure i set up a new free email address on my phone anything like hotmail or yahoo will work. I then emailed the V Card from documents on the Mac to my new email address. Opened the e-mail on my iPhone and downloaded the attachment and it gives you the option to add all contacts.
Do this and they will all be restored. Hope this helps