To solve this problem, I wrote this iptables front-end to block undesired applications from accessing the network.
DroidWall - Android Firewall is a front-end application for the powerful iptables Linux firewall. It allows you to restrict which applications are permitted to access your data networks.
This is the perfect solution if you don't have an unlimited data plan, or just wants to see your battery lasting longer.
Download from the Android Market:
After installing, press menu and click Help for an explanation on how to use it.
UPDATE: Latest version: 1.5.5 - You can check the changelog here.
I hope this will help other people.