I did my robot using bluetooth module (bluesmurf) from sparkfun with an atmega8.
It cost about 80 dollars. The atmega8 is like a 3 dollar chip, damn shipping and bluetooth module
I got my chip from digikey.
If you go with say the atmega8 for it to have its usart synchronized with the module you have to run it at higher speeds than its default speed.
Different speeds are mentioned in the datasheet. So I'd recommend also picking up a 14.7456MHz (49US package) crystal which is the speed I'm using. You'll want to get 2 small (20pF) caps for the crystal.