If your contacts were all Google contacts, they should come right back at first sync. Gmail is the same; other mail accounts you'll obviously have to set up.
The first time that you go into the market after booting up a fresh ROM and entering your Google account credentials, you will find in the "Downloads" section links to all of your old apps, both free and paid, that you had with your Google account. If you then leave the market without installing all of them, the free ones may no longer appear - just the paid ones. Text messages are definitely cleared unless you were running an app like SMS Backup & Restore, Sprite Backup, SMS Backup+, etc., which can restore text messages. The call logs are the same, but, again, there are apps to backup and restore call logs as well.
Perhaps people should make it more clear that installing a new ROM clears all of the user data and apps from the phone, but I am pretty sure that it is mentioned in at least some of the threads you read. It's a shame if you lost data, though. I guess you know now for sure.
However, all perhaps is not lost, if you did a Nandroid backup before you wiped data. You can now run a Nandroid restore, restart the phone, and bring it back just as it was before. Then you can install apps like SMS Backup & Restore, Call Logs Backup and Restore, to back up those items (and then restore them on Kaos when you reinstall it). If you have phone contacts rather than Google contacts, there is an app called UiA Backup Contacts which can create a .CSV file on your SD card; copy that file to your PC, fire up Gmail, switch to contacts view and import the .CSV file so that all of you contacts will automatically sync with the phone.
SMS Backup & Restore - Android app on AppBrain
Call Logs Backup & Restore - Android app on AppBrain
UiA - Backup Contacts - Android app on AppBrain