I have achieved the goal of connecting an android rosjava node to a roscore running on Ubuntu via bluetooth, by:
Creating an ad-hoc bluetooth network; for this I installed the "Blueman Bluetooth Manager" following the instructions on the linked askubuntu question
To be clear, even though this would achieve it, I am not sharing the internet connection of my ubuntu machine with the android tablet, since in my scenario this experiment will run in remote areas, so I actually have the wifi turned off on both the ubuntu machine and the android tablet.
I paired a Nexus 7 Android to an aspire ubuntu netbook (which has an ioGear BT 4.0 USB mini dongle model GBU521W6)
Another detail is that in the Nexus 7, when pairing the devices you need to click on the settings and select the "Internet Access" bluetooth profile, by default it will connect only to the Media audio profile (I disabled that one also).
2014-1121 Additional Update for Ubuntu 14.04
The above instructions had worked flawlessly on Ubuntu 13.04
On 14.04 Trusty the current Blueman Bluetooth Manager has an issue in that the system status bar icon does not show up and therefore doesn't allow you to get to the Local Services dialog.
This is easily resolved by launching them from a terminal window by doing either:
blueman-services
(this should have been installed on your local /usr/bin)
(you can also launch the blueman manager by running blueman-manager)
I think now ROS is just working with ethernet TCP/IP, it doesnt not supported for bluetooth (just my opinion)
If that's the case, maybe something like ROS-Serial could help?