Does Bluetooth tethering not work, or am I doing it wrong?
Maybe this is too late for some of you but this is a solution for Android 4.2:

Basically you need TUN module since the standard configuration does not include it:
Google Play - TUN.ko installer

Bluetooth thethering - fix solution