itunes backup is done when setting up new device

I am having this problem: my iphone 4 is getting super slow, so i figured i'd erase it and start a fresh install (installing everything from scratch basically). Before doing so, I backed it up, just in case i would want to go back, however, when i first connected it to itunes after erasing it, i selected the option to set it up as a new device, giving it (naively i guess) a different name from the old backup. Now, it looks like my old backup was completely deleted, and overridden by the new one. I am so frustrated about that and was wondering if someone had a rescue plan (though i doubt it - under the mobilesync folder this backup no longer exists).

A big prize to whomever comes up with a creative solution that will enable me to recover all my SMSs/Photos/recent calls, etc.

Thanks!