After modifying /etc/bluetooth/main.conf to no avail, it turns out the “Name =” string is just in there as cruft I suppose.  After some digging it turns out there are two ways to change the name of a bluetooth device on Ubuntu 11.10+

1. Create a file named /etc/machine-info which should have the following content:

   PRETTY_HOSTNAME=<devicename>

2. Use hciconfig (for more about this, type man hciconfig or hciconfig -h):

   To view details: hciconfig hcio name
   To change it: sudo hciconfig hcio <devicename>