Well I had some success by starting the bluetooth on both devices, then "warming up" the internet connection by either firing a browser to load a page or starting mobile hot spot (not actually using through mobile hotspot's wifi) and then 7 out of 10 connections are with success.
Seems like the browser/mobile hotspot do something with the 3g connection so I can then use tethering but I am not sure what .
Hope this helps a bit.

Just to be clear this is through tethering not mobile hotspot.