The solution is simple.
Open up the AVD Manager. Edit your AVD.
Down in the hardware section, there are some properties listed with "New..." and "Delete" to the right of it.
Press New. Select Data Partition size. Set to "512MB" (the MB is required). And you're done. if you still get issues, increase your system and cache partitions too using the same method.
It's all documented right here: http://developer.android.com/guide/developing/devices/managing-avds.html