I did not set a password for the restore encrypted thing. I have tried 1234 and anything else I could come up with. I have to get back in. I accidentally deleted text messages that I need for personal reasons. I called Apple, and they basically admitted that this could happen somehow, but they had no remedy. Is this true?
It is odd that you didn't ever set up a password but when restoring, iTunes still asks for password. Here are several ways you can have a try:
Disconnect your iPhone with computer by extracting your iPhone digital cable out of the USB port.
Sign out of your iTunes account.
Connect your iPhone again back to your computer.
Sign in again with your iTunes account.
The safari settings are linked to the iTunes store brower, enabling the cookies again may fix everything and you can login no problem. To enable cookies in safari, open up the preferences and go to the privacy tab then change the “block cookies” settings. After that, you may have a chance to go without restriction to restore iPhone/iPad/iPod from encrypted backup.
If all the free methods do nothing for you, you can consider the paid iPhone backup unlocker if you don't mind to cost $49.95. You can search it on google or download the free trial version from CNET: http://download.cnet.com/iPhone-Backup-Unlocker-Standard/3000-18551_4-75811366.html