Not sure I'd want to do this with bt due to it's limited short range of most devices, but I could see something like this being possible. Have you tried to email the guy to see if he could give you more info on how he did this?
The gumstix board that he's using...or at least the gumstix board in general are pretty fast/ high end setups.
I have made the same discovery about other microcontroller but none could confirm a success interface with a PICAXE. I was trying to do the same thing as seen on this vid.
Its the same theory that I wanted to do with my project robot but the guy didnt really explain what type of materials or microcontroller he was using.
I have a BlueSmIRF from Sparkfun that was mentioned above, and have seen it used on another micros' serial port, but not used it myself. And I've seen another bluetooth device, the Aircable stuff, used on a robot with a serial port.
Doesn't seem to be any reason it wouldn't work on a PICAxe, including programming and getting feedback.
I was playing around with one of these http://www.sparkfun.com/commerce/product_info.php?products_id=158 connected to a bs2 stamp and a bluetooth key.
I was able to communicate with my windows terminal and some very dirty code with with a perl script in linux but didn't do much with it at the time. I'll see about trying it on an 18x that I have when I have some time.
edit: I've also used these http://www.sparkfun.com/commerce/product_info.php?products_id=155 which were a lot easier to use and set up.