Well, I have only used usb on this computer (Win 7) but thought I would try Bluetooth. Just to prove the point I tried connecting Bluetooth with my £0.99 dongle from ebay and had loadsa problems, some I think due to the fact that my front panel usb connections tend to drop out and reconnect intermittently. It did connect at once but dropped out again almost immediately and that was that.
Retried with my slightly more expensive ebay model (I think it cost about £1.25) connected to the rear usb port and the program could still not connect.
I deleted all my contacts on the brick then clicked on the Bluetooth icon on the taskbar and a popup window appeared, asking if I wanted to add the NXT as a device. Once I clicked on 'yes' I had no trouble connecting to NXT-G.
I then put my tiny £0.99 dongle back on and it worked! Seems to be procedure rather than hardware which is causing the difficulties. When I tried on my last computer both the dongle and brick were new so there were no existing contacts or such to cause confusion and that worked straight away.
I think that you might have to create separate connections for each user on NXT-G but I am not sure about that.