I did call the police, who weren't much help and told me that I need to go back to the scene of the crime or come to the station to file a report. Since the damage was done, I did not follow through with a police report. However, had I not been in such disbelief, I would have most likely called the police on the spot.
I try to look at all incidents, especially ones that have financial impact, as a learning experience. What could I have done better? Also, what can I do better/different in the future to have a positive impact on the outcome? Below is a list that I hope we can all learn from:
Make it easy to change passwords and access your account - Have instructions on how/where you change your email/voicemail passwords so you can do it quickly. Also, have your online account setup and easy to access so you can check your statement and/or de-activate accounts online. This could be as easy as keeping a list of local bookmarks in your browser or in a text file.
Report your phone stolen immediately - There were reports online about stolen phones being used to rack up $20,000+ worth of charges. Its hard to overcome the disbelief that your phone has been stolen, however better safe than sorry. It is best to report your phone stolen ASAP.
Get insurance - Apple Care protection extends your warranty (which I had), and is not insurance. Supposedly Apple offers some kind of insurance (according to the AT&T representative), but I am unable to find more information. Also, you may want to follow up with your home insurance provider to see if its covered ($400 may slide under your deductible though).
Use a keypad/passcode lock - I did not set the passcode on the iPhone. I know, I know...silly me. However, this passcode is easily bypassed thanks to a vulnerability described here. This has to do with the "Emergency Call" feature in the iPhone, which could be used to not only make a call even though the phone is locked (which is still the case in the latest firmware) but launch applications as well. The only other method available to get around the passcode is to restore the iPhone, which would wipe all the data off of it, but still give an attacker access to your cell service if it has not already been de-activated.