Sprint just screwed me. I changed the password on my gmail account on my computer, and then tried to change it on the Evo. Sprint store said I'd lose everything and never told me about text message backup apps. I called tech support and he never told me about text message backup apps, reset my phone and I lost all. Afterward when talking to my friend about the loss, she told me I could have had a text message backup app.

Is there any recovery at all now? Otherwise, can someone refer me to a good app for automatic text message backup?
Thanks.

I recommend 'SMS Backup'. It saves your SMS messages in your gmail account. It labels them automatically with 'SMS' and marks them as 'archived' and 'read' so they don't show in your 'new' messages folder forcing you to read them again.
You can't restore them on your phone, but they are easily searchable like any other 'archived' gmail message.
Once you have the app running you can start deleting old messages on your phone without worrying about loosing them again.