Honestly? I didn't do much in terms of backup. I copied my phone's folder over to my computer, made sure I had a correctly set up recovery image, rooted, and restored myself from there. Since then I've been able to use Titanium and the like. Rooting itself generally doesn't cause issues anyway, and it doesn't erase any applications, files or settings. Also, if I remember correctly, the Evo has some really convenient one-click solutions for rooting. You should be able to use Titanium before loading a custom ROM and before actually deleting anything. Just be sure recovery is set up(ROM manager and Clockwork Recovery) and you can root without much in terms of fear.

Your contacts are all synced with your Google account, aren't they? Whenever I load a new ROM, my contacts are all there because they were stored in my Google Contacts. Check your email address book, they should all be there. HTC does have a weird contact management app that sometimes handles it, but you shouldn't use that. If anything, if you don't have them stored in Google Contacts, you should fix that.

When I got my phone I used Bluetooth to send them over all as Phone contacts. A Phone type contact using the HTC stuff doesn't get synced. I think there is a way to convert them, though.

Ah. Export your contacts to an SD card(usually from your contacts/people app, pressing the menu button works) then, and when you import the .vcf file back, add them as Gmail contacts.

I love you. That is a wonderful, wonderful site.