Stolen phone: is changing your GMail password enough?
You should check out Lookout's Plan B app. It lets you find your phone after it is lost.

I would recommend using Seekdroid or Where's my Droid in the future.