In my experience with bluetooth tethering to Android/LineageOS I take my N900 online first and force 3.5g data by checking mail on the N900 (or any data use), after that I usually have no problem with the tethered connection. For some reason my laptop(Ubuntu) most of the time just forces the connection without needing to use the 'check mail' trick.