How do I completely start over with an iPhone? After a botched attempt at jailbreaking, then removing the jailbreak, half the stuff does not work on the iPhone (apps won't sync, iPod app crashes, Settings don't "take", sync freezes the phone for 5 minutes after iTunes says its done, etc...).  

I'd like to start over.  I will re-download the apps manually and sync all my photos, addresses, etc... after the fact.

So how do I start over?  I guess, if this was a PC, I'd be asking how to reformat the hard drive.
Does iTunes recognize your iPhone? If so, you can start (non-jailbroken), by just going to the Summary page when its plugged in and selecting restore.