Ok so I spent about an hour on this and it is FINALLY working. First let me give you a quick rundown of our system here. Keep in mind I am a programmer but I've done a little administation. We are not running a front-end server here. We just have one exchange 2003 box but it is configured for HTTP-RPC. We also have a self-signed certificate.
The first thing I noticed is that in Exchange System Manager-Global Settings-Mobile Services/Properties, Outlook Mobile Access was not enabled. I checked both boxes. After still no luck, I found some links that had me make a copy of Exchange in IIS, and import as Exchange-oma then unchecking require SSL. After making a suggested registry entry, I had to go toggle SSL back on in the iPhone. I had switched it off troubleshooting, but once I changed it back, I got a couple certificate error prompts, and after hitting accept I finally started seeing folders/mail on the iPhone.
Here are the links for the steps to create the virtual dir, and registry entry:
IIS:
http://www.chicagotech.net/troubleshooting/activesync2.htm
Registry:
http://www.chicagotech.net/troubleshooting/activesync3.htm
I'm sure there are varied issues with everyone, but hopefully this will help someone.