My android phone was stolen. How worried should I be with all my google data inside the phone? Ok, so my samsung galaxy 5 was stolen. I had gmail, calendar, twitter(tweetdeck), facebook, ... all my personal data in it. 

I didn't have any app installed that could wipe this information from a sms (tried to install PlanB through the market, but I don't think it'll work). 

I already changed my google password and I'm proceeding to change facebook and twitter as well. 

Is this enough? How much of this information (old emails, tweets, ...) are saved in the phone's memory? Can I prevent access to this just by changing my passwords?

I've blocked my SIM card with my provider, so I guess the phone currently have no internet or telephone line access. 

Here in Brazil we can also block a stolen cell phone with the IMEI number, but I don't know exactly what this means. Will this brick the phone or just prevent it from being registered in the network?
Remote wipe programs like Plan B only work if your phone still has battery and still has a data connection through the internet to download the app, if you'd pre-loaded a program like LookOut then it would work without a data connection but would still need a phone network connection to receive an SMS text message or something like that. If you've blocked your SIM and/or blocked your IMEI then it's too late to use a remote wipe program as you don't have any way to get any kind of message to your phone any more, you need to do the wipe before getting anything blocked by your phone company.

Did you have any kind of unlock code (pattern or number, or something like that)? If so that should stop the thief easily getting to any of the data on the phone itself, and if they enter the wrong code/pattern a number of times it totally locks the phone out, and you need to go online (and log in with your Google account) to unlock it. They can apparently still get to data that's directly saved on your phone if they plug the phone into a PC that has the Android Developer tools on it and use the ADB command, but even then some things like the central Accounts database are encrypted to stop them getting your passwords.

Blocking the phone via IMEI will stop anyone else being able to use the phone on a phone network, it won't do any wiping or bricking at all.

There's also your SD card, the thief can just pop that out of the phone and straight into a computer or another phone, nothing on there is protected, see this previous question for a discussion on what personally identifiable info might be on the SD card: Is there any contact information on the SD card?