Nexus 4 is not sharing internet connection (tethering), while WiFi or Bluetooth connection is successfully established
Following @Shadow's suggestion I've googled a bit more...turns out that Android >= 4.1.2 prevents you from using tethering if you are served by a virtual operator (as I am).

This is a nice post http://albertomilone.com/wordpress/?p=581 explains pretty well the situation and propose a solution based on iptables.

EDIT

Looks like this problem is solved with Android 4.4.2 as stated here