Ok,

So with the native bluetooth tethering, I turn it on.. GN is paired with my phone.. however, once I enable the tethering, the network icon shows an exclamation mark showing no internet access is available.. even though the indicator on my phone for signarl (data) is blue.

Also, in Windows 7 after pairing my phone, I could right click on the galaxy nexus device in windows and select "Control" - from there I would have an option to "Connect for internet" on the dialogue menu by right clicking.. doesn't show up in Windows 8 -

I've tried using USB tethering but im not very comfortable with USB debugging left on and its painfully slow - please help.