So the new phone is here, and I got it up and running, and what do you know, I can't install apps again. Looks like CK was right about the SD card. I threw an old 1gig I didn't realized I had in there and suddenly it will install apps from the market. Doh! I'm puzzled since I did format the card already. Does this just mean that the card is shot and I need a new one? Is there something on the card that is causing this?
I'm hoping that I can just transfer everything to the new card and be all set, but if there's something on there causing this, then that won't help.
Also, on the return, the replacement phone has a build date of almost a year after my old one. so far, everything seems in perfect order with it. I will probably just keep the new one though unless something goes wrong in the next few days.
Just to update this thread in case anyone else runs into this problem, I figured out what the problem was. While reading through another thread, I found out that apps on the SD card are stored in the android.secure folder. Looking in there, I noticed duplicates of most of my apps designated with a 1 and a 2. I went through and deleted the duplicates, and all my problems stopped. I can now install, uninstall, and restore backups. One thing though is that when I restore a backup from Titanium, it puts a duplicate on the card. I have to go through and delete them, but if it keeps working, then I'm a happy guy.