If you have insurance, report the theft to the police covering the area in which it was stolen (tell them you need the report for insurance purposes if they don't seem to want to take a report on a stolen phone), then call the insurance company (probably Asurion) and report it. Most plans replace the phone for a $50 copay.
If not, and you can't recover the phone with AndroidLost, at least call the carrier and report it stolen, so the thief can't use the phone and run your bill up.